#include "TestReachability.h"
#include <vector>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

TestReachability::TestReachability() {
	root = RTreeNewIndex();
}

TestReachability::TestReachability(DGraph& g) {
	graph = g;
	root = RTreeNewIndex();
}

/* Commented out on Dec 20, 2010
 // can be deleted after finishing this project
 bool TestReachability::read_graph(istream& inGraph)
 {
 string buf;
 string sub;
 int idx;
 int sid;
 int tid;
 int n;

 // read Forest
 graph.clear();
 getline(inGraph, buf);
 if (buf != "graph_for_greach")
 {
 cout << "BAD FILE FORMAT!" << endl;
 return false;
 }

 getline(inGraph, buf);
 istringstream(buf) >> n;
 // initialize
 for (int i = 0; i < n; i++)
 {
 graph.add_vertex(i);
 }


 sid = tid = 0;
 while (getline(inGraph, buf))
 {
 idx = buf.find(":");
 buf.erase(0, idx+2);
 while (buf.find(" ") != string::npos)
 {
 sub = buf.substr(0, buf.find(" "));
 istringstream(sub) >> tid;
 buf.erase(0, buf.find(" ")+1);
 graph.add_edge(sid, tid);
 }
 ++sid;
 }
 return true;
 }

 bool TestReachability::read_graph(istream& inForest, istream& inNonForest)
 {
 string buf;
 string sub;
 int idx;
 int sid;
 int tid;
 int n;

 // read Forest
 tree.clear();
 getline(inForest, buf);
 if (buf != "graph_for_greach")
 {
 cout << "BAD FILE FORMAT - Forest!" << endl;
 return false;
 }

 getline(inForest, buf);
 istringstream(buf) >> n;
 // initialize
 for (int i = 0; i < n; i++)
 {
 tree.add_vertex();
 graph.add_vertex();
 }


 sid = tid = 0;
 while (getline(inForest, buf))
 {
 idx = buf.find(":");
 buf.erase(0, idx+2);
 while (buf.find(" ") != string::npos)
 {
 sub = buf.substr(0, buf.find(" "));
 istringstream(sub) >> tid;
 buf.erase(0, buf.find(" ")+1);
 tree.add_edge(sid, tid);
 graph.add_edge(sid, tid);
 }
 ++sid;
 }

 // read NonForest
 getline(inNonForest, buf);
 if (buf != "graph_for_greach")
 {
 cout << "BAD FILE FORMAT - Non!" << endl;
 return false;
 }

 getline(inNonForest, buf);
 istringstream(buf) >> n;

 sid = tid = 0;
 while (getline(inNonForest, buf))
 {
 idx = buf.find(":");
 buf.erase(0, idx+2);
 while (buf.find(" ") != string::npos)
 {
 sub = buf.substr(0, buf.find(" "));
 istringstream(sub) >> tid;
 buf.erase(0, buf.find(" ")+1);
 //
 NTEList::iterator iter = NTE.find(sid);
 if (iter != NTE.end())
 {
 EdgeList& el = iter->second;
 el.push_back(tid);
 }
 else
 {
 NTE.insert(make_pair(sid, EdgeList(1, tid)));
 }
 }
 ++sid;
 }

 return true;
 }

 // can be deleted after finishing this project
 bool TestReachability::read_label(istream& in)
 {
 string buf;
 getline(in, buf);

 if (buf != "graph_label") {
 cout << "BAD FILE FORMAT!" << endl;
 return false;
 }

 int n;
 getline(in, buf);
 istringstream(buf) >> n;

 string sub;
 int vid = 0;
 int label;
 int labelIdx;
 int idx;
 while (getline(in, buf)) {
 labelIdx = 0;
 idx = buf.find(":");
 buf.erase(0, idx+2);
 while (buf.find(" ") != string::npos) {
 sub = buf.substr(0, buf.find(" "));
 istringstream(sub) >> label;
 buf.erase(0, buf.find(" ")+1);
 VertexList& vl = graph.get_vertices();
 Vertex& vex = vl[vid];
 switch (labelIdx++)
 {
 case 0:
 vex._PreN = label;
 break;
 case 1:
 vex._DFLN = label;
 break;
 case 2:
 vex._SupDFLN = label;
 break;
 default:;
 }
 }
 ++vid;
 }
 return true;
 }
 */

/* Commented out on Dec 16, 2010
 * Move to DGraphUtil.cpp
 void TestReachability::spanning__dfs2(int v, vector<bool>& visited)
 {
 visited[v] = true;
 EdgeList outEdges = graph.edges_from(v);
 for (EdgeList::iterator eit=outEdges.begin(); eit!=outEdges.end(); ++eit)
 {
 int adjV = *eit;    // id of vertext adjacent to vid
 if (visited[adjV] == false)
 {
 tree.add_edge(v, adjV);
 spanning__dfs2(adjV, visited);
 }
 else
 {
 //nonForest.add_edge(v, adjV);
 NTEList::iterator iter = NTE.find(v);
 if (iter != NTE.end())
 {
 iter->second.push_back(adjV);
 }
 else
 {
 NTE.insert(make_pair(v, EdgeList(1, adjV)));
 }
 }
 }
 }

 void TestReachability::spanning__dfs()
 {
 tree.clear();
 //nonForest.clear();
 cout << graph.number_of_vertices() << endl;
 for (int i=0; i<graph.number_of_vertices(); ++i)
 {
 tree.add_vertex();
 //nonForest.add_vertex();
 }

 vector<int> roots = graph.get_roots();
 vector<bool> visited(graph.number_of_vertices(), false);

 for (vector<int>::iterator rit=roots.begin(); rit!=roots.end(); ++rit)
 {
 spanning__dfs2(*rit, visited);
 }

 // After generate a spanning tree by left-most dfs, we have to
 // reverse the order of the adjacent vertices of each vertex, because
 // all the NTEs are from right to left
 for (int v=0; v<tree.number_of_vertices(); ++v)
 {
 EdgeList& olist = tree.edges_from(v);
 // reverse this vector
 reverse(olist.begin(), olist.end());
 }
 }
 */

bool lessPreN(const pair<int, int>& p1, const pair<int, int>& p2)
/* first: _ID, second, _PreN*/
{
	if (p1.second < p2.second)
		return true;
	else
		return false;
}

// bool lessPreN(const int& p1, const int& p2)
// /* first: _ID, second, _PreN*/
// {
// 	if (graph[p1]._PreN < graph[p2]._PreN)
// 		return true;
// 	else
// 		return false;
// }

bool greaterPreN(const pair<int, int>& p1, const pair<int, int>& p2) {
	if (p1.second > p2.second)
		return true;
	else
		return false;
}

bool greaterPreN_vertices(const Vertex& p1, const Vertex& p2) {
	if (p1._PreN > p2._PreN)
		return true;
	else
		return false;
}
bool dfln_vertices(const Vertex& p1, const Vertex& p2) {
	if (p1._DFLN < p2._DFLN)
		return true;
	else
		return false;
}
/*
 * Commented out on Dec 20, 2010
 void TestReachability::sort_edges(int v)
 {
 if (v > graph.number_of_vertices())
 return;
 EdgeList& el = graph.edges_from(v);

 //el = nonForest.edges_from(v);
 //sort(el.begin(), el.end(), lessPreN);
 //el = tree.edges_from(v);
 //sort(el.begin(), el.end(), lessPreN);

 vector<pair<int, int> > adjVL;
 for (EdgeList::iterator eit=el.begin(); eit!=el.end(); ++eit)
 {
 Vertex& vex = graph[*eit];
 adjVL.push_back(make_pair(*eit, vex._PreN));
 }
 sort(adjVL.begin(), adjVL.end(), lessPreN);
 el.clear();
 for (vector<pair<int, int> >::iterator it=adjVL.begin(); it!=adjVL.end(); ++it)
 {
 el.push_back(it->first);
 }
 }
 */
//
///// sort NTEs heading from a specific vertex v in ascending order of _PreN
//void TestReachability::sort_NTEs(int v) {
//	if (v > graph.number_of_vertices())
//		return;
//	NTEList& NTE = graph.get_NTEs();
//	NTEList::iterator it = NTE.find(v);
//	if (it != NTE.end()) {
//		// found
//		EdgeList& el = it->second;
//		// sort in ascending order of _PreN
//		vector<pair<int, int> > adjVL;
//		for (EdgeList::iterator eit = el.begin(); eit != el.end(); ++eit) {
//			Vertex& vex = graph[*eit];
//			adjVL.push_back(make_pair(*eit, vex._PreN));
//		}
//		sort(adjVL.begin(), adjVL.end(), lessPreN);
//		el.clear();
//		for (vector<pair<int, int> >::iterator it = adjVL.begin(); it
//				!= adjVL.end(); ++it) {
//			el.push_back(it->first);
//		}
//	}
//}

///// remove forward edges /*and redundant intersecting edges*/
//void TestReachability::reduce_NTEs() {
//	DTree& tree = graph.get_tree();
//	NTEList& NTE = graph.get_NTEs();
//	stack<int> toBeErased;
//	// All NTEs have been sorted in ascending order of _PreN in interval_label
//	for (NTEList::iterator nit = NTE.begin(); nit != NTE.end(); ++nit) {
//		int u = nit->first;
//		EdgeList& el = nit->second;
//		// curr is the ID of the tailing vertex of the current non-redudant edge
//		// heading from u, with which other edges are to be compared
//		int curr = -1;
//		// find first curr: ID of the tailing vertex of the first non-forward edge
//		EdgeList::iterator eit = el.begin();
//		int idx = 0;
//		while (true) {
//			int v = *eit;
//			// To check whether <u,v> is a forward edge, i.e. u is father of v
//			if (tree[u]._IntBeg < tree[v]._IntBeg && tree[u]._IntEnd
//					>= tree[v]._IntEnd) {
//				el.erase(eit);
//				if (el.empty()) {
//					toBeErased.push(u);
//					break;
//				} else
//					eit = el.begin();
//			} else {
//				curr = v;
//				++idx;
//				break;
//			}
//		}
//		/*
//		 * Commented out on Dec 20th, 2010:
//		 * not take care of redundant edges other than forward edges
//		 // for
//		 for (; eit!=el.end(); ++eit)
//		 {
//		 int v = *eit;
//		 // To check whether <u,v> is redudant because thereis another <u,curr> s.t.
//		 // curr is father of v
//		 if (tree[curr]._IntBeg<tree[v]._IntBeg && tree[curr]._IntEnd>=tree[v]._IntEnd)
//		 {
//		 el.erase(eit);
//		 eit = el.begin() + idx;
//		 }
//		 // if <u,v> is not redundant compared with <u,curr>, then re-assign curr
//		 else
//		 {
//		 curr = v; ++idx;
//		 }
//		 }
//		 */
//	}
//	// Remove those entries with empty EdgeList
//	while (!toBeErased.empty()) {
//		int w = toBeErased.top();
//		toBeErased.pop();
//		NTEList::iterator nit = NTE.find(w);
//		if (nit != NTE.end())
//			NTE.erase(nit);
//	}
//}
//
///// Divide NTEs heading from a specific vertex v into 2 categories
//void TestReachability::divide_NTEs_of(int v) {
//	// All NTEs have been sorted in ascending order of _PreN in interval_label
//	DTree& tree = graph.get_tree();
//	NTEList& NTE = graph.get_NTEs();
//	SNTEList& shortNTE = graph.get_short_NTEs();
//	LNTEList& longNTE = graph.get_long_NTEs();
//	NTEList::iterator it = NTE.find(v);
//	if (it != NTE.end()) {
//		EdgeList& el = it->second;
//		for (EdgeList::iterator eit = el.begin(); eit != el.end(); ++eit) {
//			int w = *eit;
//			if (tree[v]._RangeSNTE._start <= tree[w]._PreN && tree[w]._PreN
//					<= tree[v]._RangeSNTE._end) {
//				// vertex w's _PreN falls in vertex v's _RangeSNTE: <v,w> is a short NTE
//				SNTEList::iterator sit = shortNTE.find(v);
//				if (sit == shortNTE.end()) {
//					shortNTE.insert(make_pair(v, EdgeList(1, w)));
//				} else {
//					EdgeList& sel = sit->second;
//					sel.push_back(w);
//				}
//
//			} else // otherwise, <v,w> is a long NTE
//			{
//				LNTEList::iterator lit = longNTE.find(v);
//				if (lit == longNTE.end()) {
//					longNTE.insert(make_pair(v, EdgeList(1, w)));
//				} else {
//					EdgeList& lel = lit->second;
//					lel.push_back(w);
//				}
//			}
//		}
//	}
//}
//
//void TestReachability::divide_NTEs2(
///*NTEList& NTE, SNTEList& shortNTE, LNTEList& longNTE, */int u, stack<int>& stk) {
//	DTree& tree = graph.get_tree();
//	Children cl = tree.children_of(u);
//	// if u is leaf node
//	if (cl.size() == 0) {
//		if (!stk.empty()) {
//			const int& v = stk.top();
//			stk.pop();
//			tree[u]._RangeSNTE._start = tree[v]._PreN;
//			int lmd = tree[v]._LmdID;
//			tree[u]._RangeSNTE._end = tree[lmd]._PreN;
//			// determine whether NTEs heading from u are short or long NTEs
//			divide_NTEs_of(u);
//		}
//	}
//	// if u has only one child
//	else if (cl.size() == 1) {
//		int v = cl[0];
//		divide_NTEs2(v, stk);
//		tree[u]._RangeSNTE._start = tree[v]._RangeSNTE._start;
//		tree[u]._RangeSNTE._end = tree[v]._RangeSNTE._end;
//		// determine whether NTEs heading from u are short or long NTEs
//		divide_NTEs_of(u);
//	}
//	// if u has more than one child
//	else {
//		for (Children::size_type c = 0; c < cl.size(); ++c) {
//			int v = cl[c];
//
//			if (c < cl.size() - 1) {
//				int w = cl[c + 1];
//				stk.push(w); // push his right sibling into stack
//			}
//
//			divide_NTEs2(v, stk);
//			if (c == cl.size() - 1) {
//				//stk.pop();
//				tree[u]._RangeSNTE._start = tree[v]._RangeSNTE._start;
//				tree[u]._RangeSNTE._end = tree[v]._RangeSNTE._end;
//				// determine whether NTEs heading from u are short or long NTEs
//				divide_NTEs_of(u);
//			}
//		}
//	}
//}
//
///// Divide all NTEs into 2 categories: short NTEs and long NTEs
//void TestReachability::divide_NTEs(/*NTEList& NTE, SNTEList& shortNTE, LNTEList& longNTE*/) {
//	//NTEList& NTE = graph.get_NTEs();
//	//SNTEList& shortNTE = graph.get_short_NTEs();
//	//LNTEList& longNTE = graph.get_long_NTEs();
//	DTree& tree = graph.get_tree();
//
//	// step 1: if tree is actually a forest, then add a virtual node to make it a tree
//	vector<int> roots = tree.get_roots();
//	int vr = tree.number_of_vertices();
//	tree.add_vertex(vr);
//	for (vector<int>::size_type i = 0; i != roots.size(); ++i) {
//		tree.add_edge(vr, roots[i]);
//	}
//
//	// step 2:
//	stack<int> stk;
//	divide_NTEs2(/*NTE, shortNTE, longNTE, */vr, stk);
//
//	// step 3: remove the virtual node added in step 1.
//	tree.remove_vertex(vr);
//}
//
///// Label each vertext of the tree using an interval
////int TestReachability::label_interval2(int v, int& count, vector<bool>& visited, vector<int>& vec_lmd)
//int TestReachability::label_interval2(DTree& tree, int v, int& count, vector<
//		bool>& visited, vector<int>& vec_lmd) {
//	visited[v] = true;
//	// set _IntBeg
//	//DTree& tree = graph.get_tree();
//	TreeNode& vex = tree[v];
//	vex._IntBeg = count++;
//	vex._PreN = vex._IntBeg;
//	//
//	Children sons = tree.children_of(v);
//	if (sons.size() == 0) {
//		// leaf node, set _IntEnd
//		vex._IntEnd = vex._IntBeg;
//		// the left-most descendant is itself
//		vec_lmd[v] = v;
//		tree[v]._LmdID = v;
//	}
//
//	else {
//		// non-leaf node
//		bool isFirstChild = true;
//		int ret;
//		for (Children::iterator sit = sons.begin(); sit != sons.end(); ++sit) {
//			// as it is tree, there's no need to check if the current node has already been visited
//			if (visited[*sit] == false) {
//				//ret = label_interval2(*sit, count, visited, vec_lmd);
//				ret = label_interval2(tree, *sit, count, visited, vec_lmd);
//				if (isFirstChild) {
//					vec_lmd[v] = vec_lmd[*sit];
//					tree[v]._LmdID = tree[*sit]._LmdID;
//					isFirstChild = false;
//				}
//				/*
//				 if (ret > vex._IntEnd)  // actually there's no need to check it
//				 vex._IntEnd = ret;
//				 */
//			}
//		}
//		vex._IntEnd = ret;
//	}
//	/*
//	 // for test: print the labels
//	 cout << v << "._Int = [" << vex._IntBeg << ", " << vex._IntEnd << "]" << endl;
//	 */
//	//graph[v]._IntBeg = vex._IntBeg;
//	//graph[v]._IntEnd = vex._IntEnd;
//	graph[v]._PreN = vex._PreN;
//	tree[v]._IntBeg = vex._IntBeg;
//	tree[v]._IntEnd = vex._IntEnd;
//	tree[v]._PreN = vex._PreN;
//	return vex._IntEnd;
//}

/// Assign to each vertex of the spanning tree an interval label,
/// and at the same time determine the left-most descendant of each vertex.
///// After that NTEs of each vertex are sorted in ascending order of _PreN
//void TestReachability::label_interval(vector<int>& vec_lmd) {
//	DTree& tree = graph.get_tree();
//	vector<int> roots = tree.get_roots();
//	vector<bool> visited(tree.number_of_vertices(), false);
//
//	int count = 1;
//	for (vector<int>::const_iterator rit = roots.begin(); rit != roots.end(); ++rit) {
//		//label_interval2(*rit, count, visited, vec_lmd);
//		label_interval2(tree, *rit, count, visited, vec_lmd);
//	}
//	// sort NTEs in ascending order of _PreN
//	NTEList& NTE = graph.get_NTEs();
//	for (NTEList::iterator it = NTE.begin(); it != NTE.end(); ++it) {
//		int v = it->first;
//		sort_NTEs(v);
//	}
//	/*
//	 // for test
//	 cout << "\nAfter labeling intervals the tree is: " << endl;
//	 graph.write_tree(cout);
//	 */
//}

//int TestReachability::label_dfs2(int vid, int& N, vector<bool>& visited)
void TestReachability::label_dfs2(DTree& tree, SNTEList& shortNTE, int vid,
		int& N, vector<bool>& visited) {
	Vertex& vex = graph[vid];
	visited[vid] = true;

	Children& cl = tree.children_of(vid);

	// Non-leaf node
	// 1. walk through TEs first
	for (Children::reverse_iterator cit = cl.rbegin(); cit != cl.rend(); ++cit) {
		int w = *cit;
		//		gsucc[vid].insert(w);
		if (visited[w] == false)
			label_dfs2(tree, shortNTE, w, N, visited);
		//		gsucc[vid].insert(gsucc[w].begin(), gsucc[w].end());
	}
	// 2. walk through short NTEs next
	SNTEList::iterator sit = shortNTE.find(vid);
	if (sit != shortNTE.end()) {
		// if there's any short NTEs
		EdgeList& el = sit->second;
		for (EdgeList::iterator eit = el.begin(); eit != el.end(); ++eit) {
			int w = *eit;
			//			gsucc[vid].insert(w);
			if (visited[w] == false)
				label_dfs2(tree, shortNTE, w, N, visited);
			//			gsucc[vid].insert(gsucc[w].begin(), gsucc[w].end());
		}
	}

	vex._DFLN = N;

	--N;

}

///
void TestReachability::label_dfs() {
	DTree& tree = graph.get_tree();
	SNTEList& shortNTE = graph.get_short_NTEs();
	vector<bool> visited(tree.number_of_vertices(), false);
	int N = tree.number_of_vertices();

	vector<int> roots = tree.get_roots();
	for (vector<int>::reverse_iterator rit = roots.rbegin(); rit
			!= roots.rend(); ++rit) {
		label_dfs2(tree, shortNTE, *rit, N, visited);
	}

}

/*
 * Commented out on Dec 21, 2010
 /// Implement the multiple interval labeling scheme by Rakesh Agrawarl's paper on SIGMOD'89
 /// For the use of computing predecessors and successors
 vector<vector<Interval> > TestReachability::label_multiple_interval()
 {
 DTree& tree = graph.get_tree();
 // initialize multiple interval list of each vertex
 vector<vector<Interval> > mil(graph.number_of_vertices());
 for (int i=0; i<tree.number_of_vertices(); ++i)
 {
 Interval interval;
 interval._beg = tree[i]._IntBeg;
 interval._end = tree[i]._IntEnd;
 mil[i].push_back(interval);
 }
 //
 vector<int> rts(graph.number_of_vertices());
 DGraphUtil::topological_sort(graph, rts);
 NTEList& NTE = graph.get_NTEs();

 cout << "\nReverse topological order:" << endl;
 for (vector<int>::size_type i=0; i<rts.size(); ++i)
 {
 cout << "rts[" << i << "] = " << rts[i] << endl;
 }

 for (vector<int>::size_type i=0; i<rts.size(); ++i)
 {
 //rts[i] is the ith vertex on the reverse topological order
 int u = rts[i];
 vector<Interval>& u_mil = mil[u];
 NTEList::iterator nit = NTE.find(u);
 if (nit != NTE.end())
 {
 // There's NTEs heading from u
 EdgeList& el = nit->second;
 // for each adjacent vertex v of u
 for (EdgeList::iterator eit=el.begin(); eit!=el.end(); ++eit)
 {
 // Add each interval of v to u's interval list,
 // if this interval is not included by any interval of u
 int v = *eit;
 vector<Interval>& v_mil = mil[v];
 // to check each interval v_int associated with v that if there's
 // interval u_int associated with u s.t. u_int includes v_int
 for (vector<Interval>::size_type j=0; j<v_mil.size(); ++ j)
 {
 Interval v_int = v_mil[j];
 // add v_int to mil[u]
 // mil[u].push_back(v_int);
 vector<Interval>::size_type k;
 vector<Interval>::iterator it;
 for (k=0, it=u_mil.begin(); k<u_mil.size(), it!=u_mil.end(); ++k, ++it)
 {
 Interval u_int = u_mil[k];
 if (u_int._beg>v_int._beg && u_int._end<=v_int._end)
 {
 // u_int is subsumed by v_int, delete u_int and add v_int
 u_mil.erase(it);
 u_mil.push_back(v_int);
 it = u_mil.begin() + k - 1;     // Must understand this
 }
 else if (u_int._beg<v_int._beg && u_int._end>=v_int._end)
 {
 // u_int sumsumes v_int
 continue; // v_int willnot be added at this time
 }
 else
 {
 // u_int subsumes v_int
 u_mil.push_back(v_int);
 }
 }
 } //for (vector<Intervl>::size_type j=0; j<v_mil.size(); ++ j)
 } //for (EdgeList::iterator eit=el.begin(); eit!=el.end(); ++eit)
 } //if (nit != NTE.end())
 } //for (vector<int>::size_type i=0; i<rts.size(); ++i)

 // output all the intervals of all vertices
 for (int u=0; u<graph.number_of_vertices(); ++u)
 {
 vector<Interval> u_mil = mil[u];
 cout << "Intervals of vertex " << u << ": \n\t";
 for (vector<Interval>::size_type k=0; k<u_mil.size(); ++k)
 {
 Interval u_int = u_mil[k];
 cout << "<" << u_int._beg << "," << u_int._end << ">  ";
 }
 cout << endl;
 }


 // After assigning multiple intervals, test that
 DGraphUtil::transitive_closure_matrix(graph, tcm);
 // output tcm for test
 cout << endl;
 for (map<pair<int, int>, bool >::iterator it=tcm.begin(); it!=tcm.end(); ++it)
 {
 pair<pair<int, int>, bool> pp = *it;
 pair<int, int> p = pp.first;
 cout << "<" << p.first << "," << p.second << ">: " << pp.second << endl;
 }
 cout << endl;
 bool res_tcm, res_comp;
 for (int u=0; u<graph.number_of_vertices(); ++u)
 {
 for (int v=0; v<graph.number_of_vertices(); ++v)
 {
 if (u == v)
 res_comp = true;
 else
 {
 // test whether src reaches trg by use of multiple intervals
 res_comp = false;
 vector<Interval> u_mil = mil[u];
 vector<Interval> v_mil = mil[v];
 Interval u_int, v_int;
 // check whether there's any interval v_int included by one interval u_int
 for (vector<Interval>::size_type i=0; i<v_mil.size(); ++i)
 {
 v_int = v_mil[i];
 for (vector<Interval>::size_type j=0; j<u_mil.size(); ++j)
 {
 u_int = u_mil[j];
 if (u_int._beg<v_int._beg && u_int._end>=v_int._end)
 {
 res_comp = true; break;
 }
 }
 if (res_comp)
 break;
 }
 // get reachability result from tcm
 map<pair<int, int>, bool>::iterator it = tcm.find(make_pair(u, v));
 if (it!=tcm.end())
 {
 res_tcm = it->second;
 }
 // compare res_comp with res_tcm
 if (res_comp != res_tcm)
 {
 cout << "\nTest of <" << u <<  "," << v << "> Failed!" << endl;
 cout << "res_comp = " << res_comp << "; res_tcm = " << res_tcm << endl;
 }


 }
 }
 }

 return mil;
 }

 ///
 void TestReachability::compute_successors(vector<EdgeList>& succ)
 {

 }

 ///
 void TestReachability::compute_predecessors(vector<EdgeList>& pred)
 {

 }
 */

void TestReachability::uncovered_transitive_closure(map<int, PredList>& upred,
		map<int, SuccList>& usucc, map<int, SuccList>& gsucc) {
	//	/*
	//	 DGraph tc(graph.number_of_vertices());
	//	 DGraphUtil::transitive_closure(graph, tc);
	//	 */
	//	upred.clear();
	//	usucc.clear();
	//	//	gpred.clear();
	//	gsucc.clear();
	//
	//	int yuan = 0;
	//	int hou = 0;
	//
	//	//	map<int, PredList>& upred_temp;
	//	//	map<int, vector<pair<int, int> > > usucc_temp;
	//	//	map<int, vector<pair<int, int> > > usucc_temp_2;
	//
	//	vector<pair<int, int> > usucc_t;
	//
	//	//	cout << "compute transitive closure matrix" << endl;
	//	DGraphUtil::transitive_closure_matrix(graph, _tcm);
	//
	//	for (hash_set<int>::iterator sits = graph.lnte_nodes.begin(); sits
	//			!= graph.lnte_nodes.end(); sits++) {
	//		gsucc[*sits].push_back(*sits);
	//		//	gpred[*sits].push_back(*sits);
	//		for (hash_set<int>::iterator site = graph.lnte_nodes.begin(); site
	//				!= graph.lnte_nodes.end(); site++) {
	//			if (*sits != *site) {
	//				if (_tcm[make_pair(*sits, *site)]) {
	//					if (graph[*sits]._PreN <= graph[*site]._PreN
	//							&& graph[*sits]._DFLN <= graph[*site]._DFLN) {
	//						gsucc[*sits].push_back(*site);
	//						//		gpred[*site].push_back(*sits);
	//					} else {
	//						//						usucc_temp[*site].push_back(make_pair(*sits,graph[*sits]._PreN));
	//						usucc_t.push_back(make_pair(*sits, *site));
	//						yuan++;
	//						//	usucc[*sits].push_back(*site);
	//						//	upred[*site].push_back(*sits);
	//					}
	//				}
	//			}
	//		}
	//	}
	//
	//	for (vector<pair<int, int> >::iterator it1 = usucc_t.begin(); it1
	//			!= usucc_t.end(); it1++) {
	//		bool deleteFlag = false;
	//		for (vector<pair<int, int> >::iterator it2 = usucc_t.begin(); it2
	//				!= usucc_t.end(); it2++) {
	//			if (it1 != it2) {
	//				if (graph.reachViaTree(it1->first, it2->first)
	//						&& graph.reachViaTree(it2->second, it1->second)) {
	//					deleteFlag = true;
	//					break;
	//				}
	//
	//			}
	//		}
	//		if (!deleteFlag) {
	//			usucc[it1->first].push_back(it1->second);
	//			upred[it1->second].push_back(it1->first);
	//			hou++;
	//		}
	//	}
	//
	//	//	for(map<int, vector<pair<int,int> > >::iterator tit=usucc_temp.begin();tit!=usucc_temp.end();tit++){
	//	//		int snode=tit->first;
	//	//		vector<pair<int,int> >& sv=tit->second;
	//	//		sort(sv.begin(),sv.end(),lessPreN);
	//	//
	//	//		for(int i=0;i<(signed)sv.size();i++){
	//	//			bool deleteFlag=false;
	//	//			for(int j=i+1;j<(signed)sv.size();j++){
	//	//				if(graph[sv[i].first]._DFLN<graph[sv[j].first]._DFLN){
	//	//					deleteFlag=true;
	//	//					break;
	//	//				}
	//	//			}
	//	//			if(!deleteFlag)
	//	//				usucc_temp_2[i].push_back(make_pair(snode,graph[snode]._PreN));
	//	//		}
	//	//	}
	//	//
	//	//
	//	//	for(map<int, vector<pair<int,int> > >::iterator tit=usucc_temp_2.begin();tit!=usucc_temp_2.end();tit++){
	//	//		int snode=tit->first;
	//	//		vector<pair<int,int> >& sv=tit->second;
	//	//		sort(sv.begin(),sv.end(),greaterPreN);
	//	//
	//	//		for(int i=0;i<(signed)sv.size();i++){
	//	//			bool deleteFlag=false;
	//	//			for(int j=i+1;j<(signed)sv.size();j++){
	//	//				if(graph[sv[j].first]._DFLN<graph[sv[i].first]._DFLN){
	//	//					deleteFlag=true;
	//	//					break;
	//	//				}
	//	//			}
	//	//			if(!deleteFlag){
	//	//				usucc[snode].push_back(sv[i].first);
	//	//				upred[sv[i].first].push_back(snode);
	//	//				hou++;
	//	//			}
	//	//		}
	//	//	}
	//
	//
	//	cout << "yuan:" << yuan << "\thou:" << hou << endl;
	//	//	for(map<int, vector<int> >::iterator tit=usucc.begin();tit!=usucc.end();tit++){
	//	//		int snode=tit->first;
	//	//		vector<int>& sv=tit->second;
	//	//		sort(sv.begin(),sv.end(),);
	//	//
	//	//		for(int i=0;i<(signed)sv.size();i++){
	//	//			bool deleteFlag=false;
	//	//			for(int j=i+1;j<(signed)sv.size();j++){
	//	//				if(graph[sv[i]]._DFLN<graph[sv[j]]._DFLN){
	//	//					deleteFlag=true;
	//	//					break;
	//	//				}
	//	//			}
	//	//			if(!deleteFlag)
	//	//				usucc[i].push_back(snode);
	//	//		}
	//	//	}

}

/*
 ///
 GridHop TestReachability::find_grid_hop2(DTree& tree, NTEList& NTE, int r, vector<bool>& visited,
 map<int, PredList>& predecessors, map<int, SuccList>& successors successors)
 {
 visited[r] = true;
 GridHop resHop, currHop;
 // initilaize resHop and compute density(resHop)
 resHop._hop_start = resHop._hop_end = r;
 map<int, PredList>::iterator pred_it = predecessors.find(r);
 map<int, SuccList>::iterator succ_it = successors.fidn(r);
 if (pred_it!=predecessors.end() && succ_it!=successors.end())
 {
 int sizeCin = pred_it->second.size();
 int sizeCout = succ_it->second.size();
 resHop._density = ( (double)sizeCin*sizeCout ) / ( (double)sizeCin+sizeCout );
 }
 else if (pred_it!=predecessors.end() && succ_it==successors.end())
 {
 int sizeCin = pred_it->second.size();
 int sizeCout = 1;
 resHop._density = ( (double)sizeCin*sizeCout ) / ( (double)sizeCin+sizeCout );
 }
 else if (pred_it==predecessors.end() && succ_it!=successors.end())
 {
 int sizeCin = 1;
 int sizeCout = succ_it->second.size();
 resHop._density = ( (double)sizeCin*sizeCout ) / ( (double)sizeCin+sizeCout );
 }
 else // pred_it==predecessors.end() && succ_it==successors.end()
 {
 resHop._density = 0.0;
 }

 //
 }

 ///
 GridHop TestReachability::find_grid_hop(map<int, PredList>& predecessors, map<int, SuccList>& successors)
 {
 DTree& tree = graph.get_tree();
 NTEList& NTE = graph.get_NTEs();
 vector<bool> visited(graph.number_of_vertices(), false);
 vector<int> roots = tree.get_roots();
 // for each root vertex r of G do
 GridHop resHop, currHop;
 int r = roots[0];
 // initialize resHop
 resHop._hop_start = resHop._hop_end = r;
 resHop._density = 0;
 // for each root vertex r of G do
 for (vector<int>::iterator rit=roots.begin(); rit!=roots.end(); ++rit)
 {
 r = *rit;
 currHop = find_grid_hop2(tree, NTE, r, visited, predecessors, successors);
 if (currHop._density > resHop._density)
 {
 resHop._hop_start = currHop._hop_start;
 resHop._hop_end = currHop._hop_end;
 resHop._density = currHop._density;
 }
 }
 //
 return resHop;
 }
 */

double TestReachability::hop_density_1(int u, int v, map<int, PredList>& pred,
		map<int, SuccList>& succ) {
	double density;
	map<int, PredList>::iterator pred_it = pred.find(u);
	map<int, SuccList>::iterator succ_it = succ.find(v);
	if (pred_it != pred.end() && succ_it != succ.end()) {
		int sizeCin = pred_it->second.size();
		int sizeCout = succ_it->second.size();
		density = ((double) sizeCin * sizeCout) / ((double) sizeCin + sizeCout);
	} else if (pred_it != pred.end() && succ_it == succ.end()) {
		int sizeCin = pred_it->second.size();
		int sizeCout = 1;
		density = ((double) sizeCin * sizeCout) / ((double) sizeCin + sizeCout);
	} else if (pred_it == pred.end() && succ_it != succ.end()) {
		int sizeCin = 1;
		int sizeCout = succ_it->second.size();
		density = ((double) sizeCin * sizeCout) / ((double) sizeCin + sizeCout);
	} else // pred_it==predecessors.end() && succ_it==successors.end()
	{
		density = 0.0;
	}

	return density;
}

double TestReachability::hop_density_2(int u, int v, map<int, PredList>& pred,
		map<int, SuccList>& succ) {
	double density;
	map<int, PredList>::iterator pred_it = pred.find(u);
	map<int, SuccList>::iterator succ_it = succ.find(v);
	// Covered reachable pairs:
	// upred(u) -gh-> u -gg-> v -gh-> usucc(v)
	// Note that u is not in upred(u) and v is not in usucc(v)
	// Note that u is not in either Lout(u) or Lin(u)
	// #(covererable reachable pairs)
	// = |upred(u)|*|usucc(v)| -- cover <src,trg> where src is in upred(u) and trg is in usucc(v)
	// + |upred(u)| * 1 -- cover <src,v> where src is in upred(u)
	// + 1 * |usucc(v)| -- cover <u,trg> where trg is in usucc(v)
	// Note that u-gg->v, so that #(covererable reachable pairs) != (|upred(u)|+1) * (|usucc(v)|+1)

	if (pred_it != pred.end() && succ_it != succ.end()) {
		// upred(u) and usucc(v) are both nonempty
		int sizeCin = pred_it->second.size();
		int sizeCout = succ_it->second.size();
		int numReach = sizeCin * sizeCout + sizeCin + sizeCout;
		int numLabel = sizeCin + sizeCout;
		density = ((double) numReach) / ((double) numLabel);
	} else if (pred_it != pred.end() && succ_it == succ.end()) {
		// upred(u) is nonempty, but usucc(v) is empty
		// #(covererable reachable pairs) =
		int sizeCin = pred_it->second.size();
		int sizeCout = 0;
		int numReach = sizeCin * (sizeCout + 1);
		int numLabel = sizeCin + sizeCout;
		density = ((double) numReach) / ((double) numLabel);
	} else if (pred_it == pred.end() && succ_it != succ.end()) {
		// usucc(v) is nonempty, but upred(u) is empty
		int sizeCin = 0;
		int sizeCout = succ_it->second.size();
		int numReach = (sizeCin + 1) * sizeCout;
		int numLabel = sizeCin + sizeCout;
		density = ((double) numReach) / ((double) numLabel);
	} else // pred_it==predecessors.end() && succ_it==successors.end()
	{
		density = 0.0;
	}
	/*
	 * Commented out on dec 23 afternoon, 2010
	 if (pred_it!=pred.end() && succ_it!=succ.end())
	 {
	 int sizeCin = pred_it->second.size();
	 int sizeCout = succ_it->second.size();
	 density = ( (double)sizeCin*sizeCout ) / ( (double)sizeCin+sizeCout );
	 }
	 else if (pred_it!=pred.end() && succ_it==succ.end())
	 {
	 int sizeCin = pred_it->second.size();
	 int sizeCout = 1;
	 density = ( (double)sizeCin*sizeCout ) / ( (double)sizeCin+sizeCout );
	 }
	 else if (pred_it==pred.end() && succ_it!=succ.end())
	 {
	 int sizeCin = 1;
	 int sizeCout = succ_it->second.size();
	 density = ( (double)sizeCin*sizeCout ) / ( (double)sizeCin+sizeCout );
	 }
	 else // pred_it==predecessors.end() && succ_it==successors.end()
	 {
	 density = 0.0;
	 }
	 */
	return density;
}

double TestReachability::hop_density_3(int u, int v, map<int, PredList>& pred,
		map<int, SuccList>& succ, map<int, PredList>& gpred,
		map<int, SuccList>& gsucc) {
	double density;
	map<int, PredList>::iterator pred_it = pred.find(u);
	map<int, SuccList>::iterator succ_it = succ.find(v);

	map<int, PredList>::iterator gsucc_it = gsucc.find(u);
	map<int, SuccList>::iterator gpred_it = gpred.find(v);

	int num_gsucc = 0;
	int num_gpred = 0;
	if (gsucc_it != gsucc.end()) {
		num_gsucc = gsucc_it->second.size();
	}
	if (gpred_it != gpred.end()) {
		num_gpred = gpred_it->second.size();
	}
	//	int numReach=

	if (pred_it != pred.end() && succ_it != succ.end()) {
		// upred(u) and usucc(v) are both nonempty
		int sizeCin = pred_it->second.size();
		int sizeCout = succ_it->second.size();
		int numReach = sizeCin * sizeCout + sizeCin + sizeCout + sizeCin
				* num_gsucc + sizeCout * num_gpred;
		int numLabel = sizeCin + sizeCout;
		density = ((double) numReach) / ((double) numLabel);
	} else if (pred_it != pred.end() && succ_it == succ.end()) {
		// upred(u) is nonempty, but usucc(v) is empty
		// #(covererable reachable pairs) =
		int sizeCin = pred_it->second.size();
		int sizeCout = 0;
		int numReach = sizeCin * (sizeCout + 1) + sizeCin * num_gsucc
				+ sizeCout * num_gpred;
		;
		int numLabel = sizeCin + sizeCout;
		density = ((double) numReach) / ((double) numLabel);
	} else if (pred_it == pred.end() && succ_it != succ.end()) {
		// usucc(v) is nonempty, but upred(u) is empty
		int sizeCin = 0;
		int sizeCout = succ_it->second.size();
		int numReach = (sizeCin + 1) * sizeCout + sizeCin * num_gsucc
				+ sizeCout * num_gpred;
		;
		int numLabel = sizeCin + sizeCout;
		density = ((double) numReach) / ((double) numLabel);
	} else // pred_it==predecessors.end() && succ_it==successors.end()
	{
		density = 0.0;
	}

	return density;
}

int TestReachability::hop_density_4(int u, int v, map<int, PredList>& pred,
		map<int, SuccList>& succ, map<int, PredList>& gpred,
		map<int, SuccList>& gsucc, int& csize) {
	//	double density;
	int cout = 0, cin = 0;
	int t = 0;
	map<int, PredList>::iterator pred_it = pred.find(u);
	map<int, SuccList>::iterator succ_it = succ.find(v);

	map<int, PredList>::iterator gsucc_it = gsucc.find(u);
	map<int, SuccList>::iterator gpred_it = gpred.find(v);

	map<int, PredList>::iterator vpred_it = pred.find(v);
	map<int, SuccList>::iterator usucc_it = succ.find(u);
	//u->usucc(v)
	if (succ_it != succ.end()) {
		SuccList::iterator usit_v = succ_it->second.begin();
		while (usit_v != succ_it->second.end()) {
			if (usucc_it != succ.end() && find(usucc_it->second.begin(),
					usucc_it->second.end(), *usit_v) != usucc_it->second.end()) {
				t++;
			}
			usit_v++;
		}
		cout = succ_it->second.size();

	}

	//upred(u)->v, ususs(v)
	if (pred_it != pred.end()) {
		PredList& ppred = pred_it->second;
		for (PredList::iterator pit = ppred.begin(); pit != ppred.end(); pit++) {
			map<int, SuccList>::iterator psuss = succ.find(*pit);
			if (psuss != succ.end() && find(psuss->second.begin(),
					psuss->second.end(), v) != psuss->second.end())
				t++;

			if (succ_it != succ.end()) {
				SuccList::iterator usit_v = succ_it->second.begin();
				while (usit_v != succ_it->second.end()) {
					if (find(psuss->second.begin(), psuss->second.end(),
							*usit_v) != psuss->second.end()) {
						t++;
					}
					usit_v++;
				}

			}

		}
		cin = pred_it->second.size();
	}

	csize = cin + cout;

	//	if (pred_it != pred.end() && succ_it != succ.end()) {
	//		// upred(u) and usucc(v) are both nonempty
	//		int sizeCin = pred_it->second.size();
	//		int sizeCout = succ_it->second.size();
	//		int numReach = sizeCin * sizeCout + sizeCin + sizeCout + sizeCin
	//				* num_gsucc + sizeCout * num_gpred;
	//		int numLabel = sizeCin + sizeCout;
	//		density = ((double) numReach) / ((double) numLabel);
	//	} else if (pred_it != pred.end() && succ_it == succ.end()) {
	//		// upred(u) is nonempty, but usucc(v) is empty
	//		// #(covererable reachable pairs) =
	//		int sizeCin = pred_it->second.size();
	//		int sizeCout = 0;
	//		int numReach = sizeCin * (sizeCout + 1) + sizeCin * num_gsucc
	//				+ sizeCout * num_gpred;
	//		;
	//		int numLabel = sizeCin + sizeCout;
	//		density = ((double) numReach) / ((double) numLabel);
	//	} else if (pred_it == pred.end() && succ_it != succ.end()) {
	//		// usucc(v) is nonempty, but upred(u) is empty
	//		int sizeCin = 0;
	//		int sizeCout = succ_it->second.size();
	//		int numReach = (sizeCin + 1) * sizeCout + sizeCin * num_gsucc
	//				+ sizeCout * num_gpred;
	//		;
	//		int numLabel = sizeCin + sizeCout;
	//		density = ((double) numReach) / ((double) numLabel);
	//	} else // pred_it==predecessors.end() && succ_it==successors.end()
	//	{
	//		density = 0.0;
	//	}

	return t;
}

double TestReachability::hop_density_5(int u, int v, map<int, PredList>& pred,
		map<int, SuccList>& succ, int selfu, int selfv) {
	double density = -1.0;
	map<int, PredList>::iterator pred_it = pred.find(u);
	map<int, SuccList>::iterator succ_it = succ.find(v);
	if (pred_it != pred.end() && succ_it != succ.end()) {
		int sizeCin = pred_it->second.size();
		int sizeCout = succ_it->second.size();
		density = 1.0 * (sizeCin * sizeCout + selfu + selfv) / (sizeCin
				+ sizeCout);
	} else if (pred_it != pred.end() && succ_it == succ.end()) {
		int sizeCin = pred_it->second.size();
		int sizeCout = 0;
		density = 1.0 * (sizeCin * sizeCout + selfu + selfv) / (sizeCin
				+ sizeCout);
	} else if (pred_it == pred.end() && succ_it != succ.end()) {
		int sizeCin = 0;
		int sizeCout = succ_it->second.size();
		density = 1.0 * (sizeCin * sizeCout + selfu + selfv) / (sizeCin
				+ sizeCout);
	} else // pred_it==predecessors.end() && succ_it==successors.end()
	{
		density = 0.0;
	}

	return density;
}

GridHop TestReachability::find_grid_hop_3(map<int, PredList>& upred, map<int,
		SuccList>& usucc, map<int, SuccList>& gsucc) {
	// usucc: uncovered successors; upred: uncovered predecessors
	// gsucc: successors covered by G[~LNTE]; gpred: predecessors covered by G[~LNTE]
	GridHop resHop, currHop;
	resHop._density = -0.1;
	//	SuccList::iterator* currGsit=NULL;
	//	map<int, SuccList>::iterator* curSuss=NULL;


	int self_covered_succ[graph.number_of_vertices()];
	int self_covered_pred[graph.number_of_vertices()];
	for (int i = 0; i < graph.number_of_vertices(); ++i) {
		self_covered_succ[i] = 0; //upred-->gsuss
		self_covered_pred[i] = 0; //gpred->ususs

		map<int, SuccList>::iterator slist_it = usucc.find(i);
		//	map<int, PredList>::iterator gplist_it = gpred.find(i);

		map<int, PredList>::iterator plist_it = upred.find(i);
		//	map<int, SuccList>::iterator gslist_it = gsucc.find(i);

		//& plist = pred[i];
		//SuccList& gslist = gsucc[i];
		if (slist_it != usucc.end()) {
			SuccList& slist = slist_it->second;

			for (SuccList::iterator sit = slist.begin(); sit != slist.end(); sit++) {

				map<int, PredList>::iterator splist_it = upred.find(*sit);
				if (splist_it != upred.end()) {
					PredList& pp = splist_it->second;
					for (PredList::iterator pit = pp.begin(); pit != pp.end(); pit++) {
						if (graph[*pit]._PreN <= graph[i]._PreN
								&& graph[*pit]._DFLN <= graph[i]._DFLN)
							self_covered_pred[i]++;

					}
				}
			}
		}
		if (plist_it != upred.end()) {
			PredList& plist = plist_it->second;
			for (PredList::iterator pit = plist.begin(); pit != plist.end(); pit++) {

				map<int, SuccList>::iterator splist_it = usucc.find(*pit);
				if (splist_it != usucc.end()) {
					SuccList& ss = splist_it->second;
					for (SuccList::iterator sit = ss.begin(); sit != ss.end(); sit++) {
						if (graph[*sit]._PreN >= graph[i]._PreN
								&& graph[*sit]._DFLN >= graph[i]._DFLN)
							self_covered_succ[i]++;

					}
				}

				//				for (SuccList::iterator gsit = gslist.begin(); gsit
				//						!= gslist.end(); gsit++) {
				//					map<int, PredList>::iterator ugplist_it = upred.find(*gsit);
				//					if (ugplist_it != upred.end()) {
				//						PredList& ugplist = ugplist_it->second;
				//						if (find(ugplist.begin(), ugplist.end(), *pit)
				//								!= ugplist.end())
				//							self_covered_succ[i]++;
				//					}
				//				}
			}
		}
	}
	//cout<<"self:"<<endl;
	//	for (int i = 0; i < graph.number_of_vertices(); ++i) {
	//		cout <<i<<":"<< self_covered_pred[i] << "\t" << self_covered_succ[i] << endl;
	//	}
	//cout<<"self end"<<endl;

	for (map<int, SuccList>::iterator gsucc_it = gsucc.begin(); gsucc_it
			!= gsucc.end(); ++gsucc_it) {
		//	cout << "---here--for" << flush << endl;
		int u = gsucc_it->first;
		SuccList& gsl = gsucc_it->second;
		for (SuccList::iterator gsit = gsl.begin(); gsit != gsl.end(); ++gsit) {
			int v = *gsit;

			currHop._hop_start = u;
			currHop._hop_end = v;

			currHop._density = hop_density_5(u, v, upred, usucc,
					self_covered_succ[u], self_covered_pred[v]);

			//			if(u==v) currHop._density/=2;
			if (currHop._density > resHop._density) {
				resHop._hop_start = currHop._hop_start;
				resHop._hop_end = currHop._hop_end;
				resHop._density = currHop._density;
				//				curSuss=&gsucc_it;
				//				currGsit=&gsit;
			} else if (currHop._density == resHop._density && currHop._hop_end
					== resHop._hop_end) {
				int v1 = resHop._hop_start;
				int v2 = currHop._hop_start;
				if (graph[v1]._PreN < graph[v2]._PreN && graph[v1]._DFLN
						< graph[v2]._DFLN) {
					resHop._hop_start = currHop._hop_start;
					resHop._hop_end = currHop._hop_end;
					//					curSuss=&gsucc_it;
					//					currGsit=&gsit;
				}
			}

			//			cout<<currHop._hop_start<<"\t"<<currHop._hop_end<<endl;
		}

	}

	if (resHop._hop_start == resHop._hop_end)
		equalEndpoints++;
	totalCheckHops++;

	map<int, SuccList>::iterator fit = gsucc.find(resHop._hop_start);

	SuccList& fgsuss = fit->second;
	fgsuss.erase(find(fgsuss.begin(), fgsuss.end(), resHop._hop_end));

	//	if(curSuss!=NULL)
	//	(*curSuss)->second.erase(*currGsit);


	return resHop;

	//	for (map<int, SuccList>::iterator gsucc_it = gsucc.begin(); gsucc_it
	//			!= gsucc.end(); ++gsucc_it) {
	//		int u = gsucc_it->first;
	//		SuccList& gsl = gsucc_it->second;
	//		for (SuccList::iterator gsit = gsl.begin(); gsit != gsl.end(); ++gsit) {
	//			int v = *gsit;
	//			currHop._hop_start = u;
	//			currHop._hop_end = v;
	//			currHop._density = -1;
	//			int csize = 0;
	//			int t = hop_density_4(u, v, upred, usucc, gpred, gsucc, csize);
	//			if (csize != 0) {
	//				currHop._density = 1.0 * (self_covered_pred[v]
	//						+ self_covered_succ[u] + t) / csize;
	//			}
	//
	//			if (currHop._density > resHop._density) {
	//				resHop._hop_start = currHop._hop_start;
	//				resHop._hop_end = currHop._hop_end;
	//				resHop._density = currHop._density;
	//				//				curSuss=&gsucc_it;
	//				//				currGsit=&gsit;
	//			} else if (currHop._density == resHop._density && currHop._hop_end
	//					== resHop._hop_end) {
	//				int v1 = resHop._hop_start;
	//				int v2 = currHop._hop_start;
	//				if (graph[v1]._PreN < graph[v2]._PreN && graph[v1]._DFLN
	//						< graph[v2]._DFLN) {
	//					resHop._hop_start = currHop._hop_start;
	//					resHop._hop_end = currHop._hop_end;
	//					//					curSuss=&gsucc_it;
	//					//					currGsit=&gsit;
	//				}
	//			}
	//		}
	//	}
	//
	//	map<int, SuccList>::iterator fit = gsucc.find(resHop._hop_start);
	//	SuccList& fgsuss = fit->second;
	//	fgsuss.erase(find(fgsuss.begin(), fgsuss.end(), resHop._hop_end));
	//
	//	//	if(curSuss!=NULL)
	//	//	(*curSuss)->second.erase(*currGsit);

	return resHop;
}

GridHop TestReachability::find_grid_hop_2(map<int, PredList>& upred, map<int,
		SuccList>& usucc, map<int, PredList>& gpred, map<int, SuccList>& gsucc) {
	// usucc: uncovered successors; upred: uncovered predecessors
	// gsucc: successors covered by G[~LNTE]; gpred: predecessors covered by G[~LNTE]
	GridHop resHop, currHop;
	resHop._density = -0.1;
	//	SuccList::iterator* currGsit=NULL;
	//	map<int, SuccList>::iterator* curSuss=NULL;


	int self_covered_succ[graph.number_of_vertices()];
	int self_covered_pred[graph.number_of_vertices()];
	for (int i = 0; i < graph.number_of_vertices(); ++i) {
		self_covered_succ[i] = 0; //upred-->gsuss
		self_covered_pred[i] = 0; //gpred->ususs

		map<int, SuccList>::iterator slist_it = usucc.find(i);
		//	map<int, PredList>::iterator gplist_it = gpred.find(i);

		map<int, PredList>::iterator plist_it = upred.find(i);
		//	map<int, SuccList>::iterator gslist_it = gsucc.find(i);

		//& plist = pred[i];
		//SuccList& gslist = gsucc[i];
		if (slist_it != usucc.end()) {
			SuccList& slist = slist_it->second;

			for (SuccList::iterator sit = slist.begin(); sit != slist.end(); sit++) {

				map<int, PredList>::iterator splist_it = upred.find(*sit);
				if (splist_it != upred.end()) {
					PredList& pp = splist_it->second;
					for (PredList::iterator pit = pp.begin(); pit != pp.end(); pit++) {
						if (graph[*pit]._PreN <= graph[i]._PreN
								&& graph[*pit]._DFLN <= graph[i]._DFLN)
							self_covered_pred[i]++;

					}
				}
			}
		}
		if (plist_it != upred.end()) {
			PredList& plist = plist_it->second;
			for (PredList::iterator pit = plist.begin(); pit != plist.end(); pit++) {

				map<int, SuccList>::iterator splist_it = usucc.find(*pit);
				if (splist_it != usucc.end()) {
					SuccList& ss = splist_it->second;
					for (SuccList::iterator sit = ss.begin(); sit != ss.end(); sit++) {
						if (graph[*sit]._PreN >= graph[i]._PreN
								&& graph[*sit]._DFLN >= graph[i]._DFLN)
							self_covered_succ[i]++;

					}
				}

				//				for (SuccList::iterator gsit = gslist.begin(); gsit
				//						!= gslist.end(); gsit++) {
				//					map<int, PredList>::iterator ugplist_it = upred.find(*gsit);
				//					if (ugplist_it != upred.end()) {
				//						PredList& ugplist = ugplist_it->second;
				//						if (find(ugplist.begin(), ugplist.end(), *pit)
				//								!= ugplist.end())
				//							self_covered_succ[i]++;
				//					}
				//				}
			}
		}
	}

	for (map<int, SuccList>::iterator gsucc_it = gsucc.begin(); gsucc_it
			!= gsucc.end(); ++gsucc_it) {
		int u = gsucc_it->first;
		SuccList& gsl = gsucc_it->second;
		for (SuccList::iterator gsit = gsl.begin(); gsit != gsl.end(); ++gsit) {
			int v = *gsit;
			currHop._hop_start = u;
			currHop._hop_end = v;
			currHop._density = -1;
			int csize = 0;
			int t = hop_density_4(u, v, upred, usucc, gpred, gsucc, csize);
			if (csize != 0) {
				currHop._density = 1.0 * (self_covered_pred[v]
						+ self_covered_succ[u] + t) / csize;
			}

			if (currHop._density > resHop._density) {
				resHop._hop_start = currHop._hop_start;
				resHop._hop_end = currHop._hop_end;
				resHop._density = currHop._density;
				//				curSuss=&gsucc_it;
				//				currGsit=&gsit;
			} else if (currHop._density == resHop._density && currHop._hop_end
					== resHop._hop_end) {
				int v1 = resHop._hop_start;
				int v2 = currHop._hop_start;
				if (graph[v1]._PreN < graph[v2]._PreN && graph[v1]._DFLN
						< graph[v2]._DFLN) {
					resHop._hop_start = currHop._hop_start;
					resHop._hop_end = currHop._hop_end;
					//					curSuss=&gsucc_it;
					//					currGsit=&gsit;
				}
			}
		}
	}

	map<int, SuccList>::iterator fit = gsucc.find(resHop._hop_start);
	SuccList& fgsuss = fit->second;
	fgsuss.erase(find(fgsuss.begin(), fgsuss.end(), resHop._hop_end));

	//	if(curSuss!=NULL)
	//	(*curSuss)->second.erase(*currGsit);

	return resHop;
}

GridHop TestReachability::find_grid_hop_1(HOPQUEUE& hops) {
	// usucc: uncovered successors; upred: uncovered predecessors
	// gsucc: successors covered by G[~LNTE]; gpred: predecessors covered by G[~LNTE]
	GridHop resHop, currHop;
	resHop._density = -0.1;
	resHop._hop_pren = graph.number_of_vertices() + 5;

	//	int up_size;
	//	int us_size;

	//	currHop=hops.top();
	//	hops.pop();
	//	resHop=currHop;

	while (!hops.empty()) {

		currHop = hops.top();

		//		cout<<"ok "<<currHop._density<<endl;
		if (resHop._density < currHop._density || (equalto(resHop._density,
				currHop._density) && resHop._hop_pren > currHop._hop_pren)) {
			hops.pop();
			//			cout<<"update"<<endl;
			if (hop_density(currHop))
				continue;
			//cout<<"update size:"<<currHop.toRemove.size()<<endl;
			if (currHop._density > resHop._density || (equalto(
					currHop._density, resHop._density) && currHop._hop_pren
					<= resHop._hop_pren)) {
				if (resHop._density > 0)
					hops.push(resHop);
				resHop = currHop;
			} else
				hops.push(currHop);
		} else
			break;
	}

	//	if (resHop._hop_start == 514 && resHop._hop_end == 513) {
	//		cout << "((((((((((()))))))))))))))))" << endl;
	//		if (contour.find(870) != contour.end() && contour[870].find(319)
	//				!= contour[870].end()) {
	//			cout << "*******************" << endl;
	//		}
	//	}

	return resHop;
}

// for test
void TestReachability::print_succ(map<int, SuccList>& succ) {
	cout << "\nReachable pairs in format of  succ: " << endl;
	for (map<int, SuccList>::iterator succ_it = succ.begin(); succ_it
			!= succ.end(); ++succ_it) {
		int src = succ_it->first;
		cout << src << ":";
		SuccList& sl = succ_it->second;
		for (SuccList::iterator sit = sl.begin(); sit != sl.end(); ++sit) {
			int trg = *sit;
			cout << " " << trg;
		}
		cout << endl;
	}
}

// for test
void TestReachability::print_pred(map<int, PredList>& pred) {
	cout << "\nReachable pairs in format of pred: " << endl;
	for (map<int, PredList>::iterator pred_it = pred.begin(); pred_it
			!= pred.end(); ++pred_it) {
		int trg = pred_it->first;
		cout << trg << ":";
		PredList& pl = pred_it->second;
		for (PredList::iterator pit = pl.begin(); pit != pl.end(); ++pit) {
			int src = *pit;
			cout << " " << src;
		}
		cout << endl;
	}
}

//void TestReachability::label2() {
//
//}


//void TestReachability::label_grid_hop() {
//	// for each vertex v od G initialize Lin(v) and Lout(v) as empty sets
//
//	for (int u = 0; u < graph.number_of_vertices(); ++u) {
//		_labels.push_back(GridHopLabel());
//	}
//	// compute the uncovered transitive closuremmfr123@163.com
//	map<int, PredList> upred, gpred;
//	map<int, SuccList> usucc, gsucc;
//	uncovered_transitive_closure(upred, usucc, gpred, gsucc);
//	// while there are still uncovered reachable pairs
//	GridHop hop;
//	int cnt = 0;
//	vector<int> srcToRemove, trgToRemove;
//	while (!usucc.empty()) {
//
//		//cout << "\nRound " << ++cnt << endl;
//		//if (cnt > 35)
//		//{
//		//cout << "here" << endl;
//		//}
//		//cout << "\nusucc.empty() = " << usucc.empty() << endl;
//		//print_succ(usucc);
//		//print_pred(upred);
//		srcToRemove.clear();
//		trgToRemove.clear();
//		hop = find_grid_hop(upred, usucc, gpred, gsucc);
//		//		cout << "grid-hop: density(" << hop._hop_start << "-->" << hop._hop_end
//		//				<< ") = " << hop._density << endl;
//		// Add to _labels
//		int x = hop._hop_start, y = hop._hop_end;
//		// add x to Lout(v) of any v in upred(x)
//		map<int, PredList>::iterator upred_it = upred.find(x);
//		if (upred_it != upred.end()) {
//			// there are still uncovered reachable pairs taling at x: <v,x>
//			PredList& upl = upred_it->second;
//			for (PredList::iterator upit = upl.begin(); upit != upl.end(); ++upit) {
//				int v = *upit;
//				// add x to Lout(v)
//				_labels[v]._Lout.insert(x);
//				// mark it to be removed
//				srcToRemove.push_back(v);
//			}
//		}
//		// add y to Lin(v) of any v in usucc(y), and remove involved reachable pairs in usucc
//		map<int, SuccList>::iterator usucc_it = usucc.find(y);
//		if (usucc_it != usucc.end()) {
//			// there are still uncovered reachable pairs heading from y: <y,v>
//			SuccList& usl = usucc_it->second;
//			for (SuccList::iterator usit = usl.begin(); usit != usl.end(); ++usit) {
//				int v = *usit;
//				// add y to Lin(v)
//				_labels[v]._Lin.insert(y);
//				// mark it to be removed
//				trgToRemove.push_back(v);
//			}
//		}
//		srcToRemove.push_back(x);
//		srcToRemove.push_back(y);
//		trgToRemove.push_back(x);
//		trgToRemove.push_back(y);
//
//		// remove reachable pairs covered by this gird-hop from usucc and upred
//		for (vector<int>::size_type i = 0; i < srcToRemove.size(); ++i) {
//			int src = srcToRemove[i];
//			for (vector<int>::size_type j = 0; j < trgToRemove.size(); ++j) {
//				int trg = trgToRemove[j];
//
//				// remove <src,trg> from usucc(src)
//				map<int, SuccList>::iterator usucc_it = usucc.find(src);
//				if (usucc_it != usucc.end()) {
//					SuccList& usl = usucc_it->second;
//					SuccList::iterator usit = find(usl.begin(), usl.end(), trg);
//					if (usit != usl.end()) {
//						usl.erase(usit);
//						if (usl.empty()) {
//							usucc.erase(usucc_it);
//							//cout << "usucc.size = " << usucc.size();
//						}
//
//					}
//				}
//				// remove <src,trg> from upred(trg)
//				map<int, PredList>::iterator upred_it = upred.find(trg);
//				if (upred_it != upred.end()) {
//
//					PredList& upl = upred_it->second;
//					if (upl.size() > 0) {
//
//						PredList::iterator upit = find(upl.begin(), upl.end(),
//								src);
//
//						if (upit != upl.end()) {
//							upl.erase(upit);
//							if (upl.empty()) {
//								upred.erase(upred_it);
//								//cout << "upred.size = " << upred.size();
//							}
//						}
//					}
//				}
//
//			}
//
//		}
//
//	}
//
//	// sort all the Lin(u) and Lout(u) in ascending order of _PreN
//	for (int u = 0; u < graph.number_of_vertices(); ++u) {
//		vector<pair<int, int> > adjVL;
//		InLabel& Lin = _labels[u]._Lin;
//		// sort Lin(u)
//		//	/	unique(Lin.begin(), Lin.end());
//		for (InLabel::iterator init = Lin.begin(); init != Lin.end(); ++init) {
//			Vertex& vex = graph[*init];
//			adjVL.push_back(make_pair(*init, vex._PreN));
//		}
//		sort(adjVL.begin(), adjVL.end(), lessPreN);
//		//cout << "Lin(" << u << ")" << ": ";
//		Lin.clear();
//		for (vector<pair<int, int> >::iterator it = adjVL.begin(); it
//				!= adjVL.end(); ++it) {
//			Lin.insert(it->first);
//			//cout << it->first << " ";
//		}
//		//cout << endl;
//		// sort Lout(u)
//		adjVL.clear();
//		OutLabel& Lout = _labels[u]._Lout;
//		//	unique(Lout.begin(), Lout.end());
//		for (OutLabel::iterator outit = Lout.begin(); outit != Lout.end(); ++outit) {
//			Vertex& vex = graph[*outit];
//			adjVL.push_back(make_pair(*outit, vex._PreN));
//		}
//		sort(adjVL.begin(), adjVL.end(), lessPreN);
//		//cout << "Lout(" << u << ")" << ": ";
//		Lout.clear();
//		for (vector<pair<int, int> >::iterator it = adjVL.begin(); it
//				!= adjVL.end(); ++it) {
//			Lout.insert(it->first);
//			//cout << it->first << " ";
//		}
//		//cout << endl;
//	}
//
//}

void TestReachability::reduceUncoveredPairs(map<int, SuccList>& usucc, map<int,
		PredList>& upred, vector<int>& srcToRemove, vector<int>& trgToRemove,
		int x, int y, int& reduced) {

	int trg = x;
	hash_set<int> toRemove;
	hash_set<int>::iterator re_it;

	for (vector<int>::size_type j = 0; j < srcToRemove.size(); ++j) {
		int src = srcToRemove[j];
		map<int, SuccList>::iterator usucc_it = usucc.find(src);

		if (usucc_it != usucc.end()) {

			SuccList& usl = usucc_it->second;
			SuccList::iterator it = usl.begin();
			for (; it != usl.end(); it++) {
				if (graph[trg]._PreN <= graph[*it]._PreN && graph[trg]._DFLN
						<= graph[*it]._DFLN) {

					map<int, PredList>::iterator upred_it = upred.find(*it);
					PredList& upl = upred_it->second;
					PredList::iterator upit = find(upl.begin(), upl.end(), src);
					if (upit != upl.end()) {
						upl.erase(upit);
						if (upl.empty()) {
							upred.erase(upred_it);
						}
					}
					toRemove.insert(*it);
					//					usl.erase(it);

				}

			}

			if (toRemove.size() > 0) {
				for (re_it = toRemove.begin(); re_it != toRemove.end(); re_it++) {
					usl.erase(*re_it);
					reduced++;
				}
				//				if (usl.empty()) {
				//					usucc.erase(usucc_it);
				//				}
				toRemove.clear();
			}
		}

	}

	int src = y;
	for (vector<int>::size_type j = 0; j < trgToRemove.size(); ++j) {
		//	cout<<"start"<<endl;
		int trg = trgToRemove[j];
		map<int, PredList>::iterator upred_it = upred.find(trg);
		if (upred_it != upred.end()) {

			PredList& upl = upred_it->second;

			PredList::iterator it = upl.begin();
			for (; it != upl.end(); it++) {
				if (graph[src]._PreN >= graph[*it]._PreN && graph[src]._DFLN
						>= graph[*it]._DFLN) {

					map<int, SuccList>::iterator usucc_it = usucc.find(*it);
					if (usucc_it != usucc.end()) {
						SuccList& usl = usucc_it->second;
						SuccList::iterator usit = find(usl.begin(), usl.end(),
								trg);
						if (usit != usl.end()) {
							usl.erase(usit);
							reduced++;

						}
					}

					toRemove.insert(*it);
					//					upl.erase(it);

					//				} else
					//					it++;
					//					if (upl.empty()) {
					//						upred.erase(upred_it);
					//						//							usucc_it
					//						//							//cout << "usucc.size = " << usucc.size();
					//					}
				}

			}

			if (toRemove.size() > 0) {
				for (re_it = toRemove.begin(); re_it != toRemove.end(); re_it++) {
					upl.erase(*re_it);
					//					reduced++;
				}
				toRemove.clear();
			}
		}
		//cout<<"end"<<endl;
	}
}

bool TestReachability::hop_density(GridHop& hop) {
	//	int remove=0;

	hop.toRemove.clear();

	int upred_size = 0;
	int usucc_size = 0;

	if (upred.find(hop._hop_start) != contour.end()) {
		PredList& preds = upred[hop._hop_start];
		upred_size = preds.size();
		if (contour.find(hop._hop_end) != contour.end()) {
			usucc_size = contour[hop._hop_end].size();
		}
		for (PredList::iterator pit = preds.begin(); pit != preds.end(); pit++) {
			SuccList& succ = contour[*pit];
			for (SuccList::iterator sit = succ.begin(); sit != succ.end(); sit++) {
				if (usucc_size > 0) {
					if (contour[hop._hop_end].find(*sit)
							!= contour[hop._hop_end].end()) {
						hop.toRemove.push_back(make_pair(*pit, *sit));
						continue;
					}
				}

				if (graph.reachViaTree(hop._hop_start, *sit)) {
					hop.toRemove.push_back(make_pair(*pit, *sit));
				} else {

					for (set<int>::iterator lin_it = _labels[*sit]._Lin.begin(); lin_it
							!= _labels[*sit]._Lin.end(); lin_it++) {
						if (graph.reachViaTree(hop._hop_start, *lin_it)) {
							hop.toRemove.push_back(make_pair(*pit, *sit));
							break;
						}
					}
				}

			}

		}
	}

	if (contour.find(hop._hop_end) != contour.end()) {
		SuccList& succ = contour[hop._hop_end];
		usucc_size = succ.size();
		for (SuccList::iterator sit = succ.begin(); sit != succ.end(); sit++) {
			PredList& preds = upred[*sit];
			for (PredList::iterator pit = preds.begin(); pit != preds.end(); pit++) {
				if ((upred_size > 0 && upred[hop._hop_start].find(*pit)
						!= upred[hop._hop_start].end()))
					continue;// avoid adding duplicate contour: upred(u)->usucc(v)
				if (graph.reachViaTree(*pit, hop._hop_end))
					hop.toRemove.push_back(make_pair(*pit, *sit));
				else {
					for (set<int>::iterator lout_it =
							_labels[*pit]._Lout.begin(); lout_it
							!= _labels[*pit]._Lout.end(); lout_it++) {
						if (graph.reachViaTree(*lout_it, hop._hop_end)) {
							hop.toRemove.push_back(make_pair(*pit, *sit));
							break;

						}
					}
				}

			}
		}

	}

	if (upred_size == 0 && usucc_size == 0) {
		return true;
	}

	hop._density = 1.0 * hop.toRemove.size() / (upred_size + usucc_size);
	return false;
}

///=========================================
void TestReachability::label_grid_hop() {
	// for each vertex v od G initialize Lin(v) and Lout(v) as empty sets


	for (int u = 0; u < graph.number_of_vertices(); ++u) {
		_labels.push_back(GridHopLabel());
	}

	GridHop hop;

	//	vector<int> srcToRemove, trgToRemove;
	//	map<pair<int,int>, vector<pair<int,int> > > hops_remove;
	//	int reduced;

	HOPQUEUE hops;
	GridHop ht;
	//	int up_size;
	//	int us_size;

	//	cout<<"init hop density "<<endl;
	for (map<int, SuccList>::iterator gsucc_mit = gsucc.begin(); gsucc_mit
			!= gsucc.end(); ++gsucc_mit) {
		ht._hop_start = gsucc_mit->first;
		ht._hop_pren = graph[ht._hop_start]._PreN;

		if (upred.find(ht._hop_start) != upred.end()) {
			//			up_size = upred[ht._hop_start].size();
			for (SuccList::iterator gsucc_it = gsucc_mit->second.begin(); gsucc_it
					!= gsucc_mit->second.end(); gsucc_it++) {
				ht._hop_end = *gsucc_it;

				if (contour.find(ht._hop_end) != contour.end()) {
					hop_density(ht);
					hops.push(ht);
				}

			}



		}

		if (upred.find(ht._hop_start) != upred.end() || contour.find(
				ht._hop_start) != contour.end()) {
			ht._hop_end = ht._hop_start;
			hop_density(ht);
//			if (ht._hop_start == 1415 && ht._hop_end == 1414)
//				cout << "*****33333";
			hops.push(ht);
		}

	}
	//cout<<"init over"<<endl;

	bool begin = true;

	//	int round = 0;
	while (left > 0) {

		if (begin) {
			hop = hops.top();
			hops.pop();
			begin = false;
		} else {
			hop = find_grid_hop_1(hops);
		}

		// Add to _labels
		int x = hop._hop_start, y = hop._hop_end;
		// add x to Lout(v) of any v in upred(x)
		map<int, PredList>::iterator upred_it = upred.find(x);
		if (upred_it != upred.end()) {
			// there are still uncovered reachable pairs taling at x: <v,x>
			PredList& upl = upred_it->second;
			for (PredList::iterator upit = upl.begin(); upit != upl.end(); ++upit) {
				int v = *upit;
				// add x to Lout(v)
				_labels[v]._Lout.insert(x);
				// mark it to be removed
				//srcToRemove.push_back(v);
			}
		}
		// add y to Lin(v) of any v in usucc(y), and remove involved reachable pairs in usucc
		map<int, SuccList>::iterator usucc_it = contour.find(y);
		if (usucc_it != contour.end()) {
			// there are still uncovered reachable pairs heading from y: <y,v>
			SuccList& usl = usucc_it->second;
			for (SuccList::iterator usit = usl.begin(); usit != usl.end(); ++usit) {
				int v = *usit;
				// add y to Lin(v)
				_labels[v]._Lin.insert(y);
				// mark it to be removed
				//	trgToRemove.push_back(v);
			}
		}

		for (vector<pair<int, int> >::iterator rit = hop.toRemove.begin(); rit
				!= hop.toRemove.end(); rit++) {
			contour[rit->first].erase(rit->second);
			upred[rit->second].erase(rit->first);
		}

		left -= hop.toRemove.size();
		hop.toRemove.clear();

	}


	cout << "remove redundant labels" << endl;
	//		 sort all the Lin(u) and Lout(u) in ascending order of _PreN
	for (int u = 0; u < graph.number_of_vertices(); ++u) {
		vector<pair<int, int> > adjVL;
		InLabel& Lin = _labels[u]._Lin;
		// sort Lin(u)
		//	/	unique(Lin.begin(), Lin.end());
		for (InLabel::iterator init = Lin.begin(); init != Lin.end(); ++init) {
			Vertex& vex = graph[*init];
			adjVL.push_back(make_pair(*init, vex._PreN));
		}
		sort(adjVL.begin(), adjVL.end(), lessPreN);
		//cout << "Lin(" << u << ")" << ": ";
		Lin.clear();
		for (vector<pair<int, int> >::iterator it = adjVL.begin(); it
				!= adjVL.end(); ++it) {
			vector<pair<int, int> >::iterator it_e = it + 1;
			bool deleteFlag = false;
			if (it != adjVL.end())
				while (it_e != adjVL.end()) {

					if (graph[it->first]._DFLN < graph[(it_e++)->first]._DFLN) {
						deleteFlag = true;
						break;
					}
				}
			if (!deleteFlag)
				Lin.insert(it->first);
			//cout << it->first << " ";
		}
		//cout << endl;
		// sort Lout(u)
		adjVL.clear();
		OutLabel& Lout = _labels[u]._Lout;
		//	unique(Lout.begin(), Lout.end());
		for (OutLabel::iterator outit = Lout.begin(); outit != Lout.end(); ++outit) {
			Vertex& vex = graph[*outit];
			adjVL.push_back(make_pair(*outit, vex._PreN));
		}

		sort(adjVL.begin(), adjVL.end(), lessPreN);
		//cout << "Lout(" << u << ")" << ": ";
		Lout.clear();
		for (vector<pair<int, int> >::iterator it = adjVL.begin(); it
				!= adjVL.end(); ++it) {
			vector<pair<int, int> >::iterator it_b = it - 1;
			bool deleteFlag = false;
			if (it != adjVL.begin())
				while (it_b != adjVL.begin()) {

					if (graph[it->first]._DFLN > graph[(it_b--)->first]._DFLN) {
						deleteFlag = true;
						break;
					}
				}
			if (!deleteFlag)
				Lout.insert(it->first);
			//cout << it->first << " ";
		}
		//cout << endl;
	}

}

/// Apply the grid-hop labeling scheme by calling other labeling functions
void TestReachability::create_label() {
	//	DTree& tree = graph.get_tree();
	//	NTEList& NTE = graph.get_NTEs();
	//	//SNTEList& shortNTE = graph.get_short_NTEs();
	//	//LNTEList& longNTE = graph.get_long_NTEs();
	//	// step 1: get a right-most spanning tree, thus graph => tree + NTE
	//	DGraphUtil::rightmost_spanning_tree(graph, tree, NTE);
	//	// step 2: label tree vertices wtih intervals
	//	vector<int> vec_lmd(graph.number_of_vertices(), -1);
	//	label_interval(vec_lmd);
	//	// step 3: reduce redudant NTEs, i.e. forward edges and redudant intersecting edges
	//	reduce_NTEs();
	//	// step 4: divide NTE into shortNTE and longNTE
	//	divide_NTEs(/*NTE, shortNTE, longNTE*/);
	//	//label_dfs();
}

/* Commented out on Dec 16, 2010
 * moved to DGraphUtil.cpp
 void TestReachability::compute_tcm()
 {
 DGraph tc(graph.number_of_vertices());
 DGraphUtil::transitive_closure(graph, tc);
 EdgeList el;
 EdgeList::iterator eit;
 for (int i = 0; i < tc.number_of_vertices(); i++)
 {
 el = tc.edges_from(i);
 for (eit = el.begin(); eit != el.end(); eit++)
 {
 _tcm[make_pair(i,*eit)] = true;

 // for test
 //cout << i << " reaches " << *eit << endl;
 //
 }
 }
 }
 */

void TestReachability::print_label(ostream& os) {
	VertexList& vl = graph.get_vertices();
	DTree& tree = graph.get_tree();
	os << "\nLabels on G[~LNTE]: " << endl;
	for (VertexList::iterator vit = vl.begin(); vit != vl.end(); ++vit) {
		Vertex& vex = *vit;
		os << "Vertex #" << vex._ID << ": _PreN=" << vex._PreN << "; _DFLN="
				<< vex._DFLN << "; ";
		os << "[_IntBeg, _IntEnd]=[" << vex._PreN << "," << vex._SupPreN << "]"
				<< endl;
	}

	// print grid-hop labels
	os << "\nGrid-Hop Labels: " << endl;
	for (vector<GridHopLabel>::size_type i = 0; i < _labels.size(); ++i) {
		InLabel& Lin = _labels[i]._Lin;
		OutLabel& Lout = _labels[i]._Lout;
		os << "**********" << endl;
		os << "Lin(" << i << ") = {";
		for (InLabel::iterator init = Lin.begin(); init != Lin.end(); ++init) {
			os << " " << *init;
		}
		os << " }" << endl;
		os << "Lout(" << i << ") = {";
		for (OutLabel::iterator outit = Lout.begin(); outit != Lout.end(); ++outit) {
			os << " " << *outit;
		}
		os << " }" << endl;
	}

	/*
	 // print grid-hop labels
	 os << "\nGrid-Hop Labels: " << endl;
	 for (vector<GridHopLabel>::size_type i=0; i<_labels.size(); ++i)
	 {
	 cout << "Vertex " << i << ": Lin(" << i << ") = "
	 }
	 */
}
//
//bool TestReachability::reach(int src, int trg) {
//	VertexList vl = graph.get_vertices();
//	Vertex& srcVex = vl[src];
//	Vertex& trgVex = vl[trg];
//
//	bool res = false;
//	if (srcVex._PreN <= trgVex._PreN && srcVex._DFLN <= trgVex._DFLN/* && trgVex._SupDFLN <= srcVex._SupDFLN*/)
//		res = true;
//	else
//		res = false;
//	return res;
//}
//
//void TestReachability::test_reach() {
//	DGraphUtil::transitive_closure_matrix(graph, _tcm);
//	bool failed = false;
//	for (int src = 0; src < graph.number_of_vertices(); ++src) {
//		for (int trg = 0; trg < graph.number_of_vertices(); ++trg) {
//			bool testResult = reach(src, trg);
//			bool finalResult = _tcm[make_pair(src, trg)];
//			if (testResult != finalResult) {
//				cout << "Failed: reach(" << src << "," << trg << ")="
//						<< testResult << ", but TCM[" << src << "," << trg
//						<< "]=" << finalResult << endl;
//				failed = true;
//			}
//		}
//	}
//	if (!failed) {
//		cout << "Success!" << endl;
//	}
//}

void TestReachability::uncovered_transitive_closure_evaluate(int& total,
		int& covered) {

	covered = 0;
	//	total = 0;

	DGraphUtil::transitive_closure_matrix(graph, _tcm);

	total = _tcm.size();
	for (map<pair<int, int> , bool>::iterator tcm_it = _tcm.begin(); tcm_it
			!= _tcm.end(); ++tcm_it) {
		pair<int, int> p = tcm_it->first;
		int src = p.first, trg = p.second;
		/*
		 if (src == trg)
		 continue;
		 */
		if (graph[src]._PreN <= graph[trg]._PreN && graph[src]._DFLN
				<= graph[trg]._DFLN) {
			covered++;
		}

	}
	//	out << total << "\t" << covered << endl;

}

int TestReachability::index_size() {

	int in_size = 0, out_size = 0;
	int N = graph.number_of_vertices();
	for (int i = 0; i < N; i++) {
		in_size += _labels[i]._Lin.size();
		out_size += _labels[i]._Lout.size();
	}
	return in_size + out_size;

}

void TestReachability::findContour(int s, int e) {
	for (map<int, hash_set<int> >::iterator mit = contour.begin(); mit
			!= contour.end(); mit++) {
		if (graph.reachViaTree(s, mit->first)) {
			for (hash_set<int>::iterator sit = mit->second.begin(); sit
					!= mit->second.end(); sit++) {
				if (graph.reachViaTree(*sit, e)) {
					cout << "found: " << mit->first << "," << *sit << endl;
					return;
				}
			}

		}
	}
	cout << "not found!" << endl;
}

// only for testing functionalities of TestReachability when programming
void TestReachability::test() {

	DTree& tree = graph.get_tree();
	DGraphUtil::rightmost_spanning_tree(graph, tree);
	label_dfs();
	//	graph.write_tree(cout);
	//	cout<<"label grid hop"<<endl;
	//	cout << "lnte_nodes:" << graph.lnte_nodes.size() << endl;
	//	gsucc.clear();
	//	cout << "gsucc size1:" << gsuccSize() << endl;
	GhopContour();

//	cout << "contour size:" << left << endl;

//	findContour(4865, 26);
	//		if(gsucc[1415].find(1414)!=gsucc[1415].end()){
	//				cout<<"****************8";
	//		}
	//		exit(0);
	//	findContour(870, 319);
	//	inputCmd();
	//	cout << "gsucc size:" << gsuccSize() << endl;

	//	graph.write_tree(cout);
	//	graph.write_short_NTEs(cout);
	//	graph.write_long_NTEs(cout);

	//			exit(0);

	label_grid_hop();
	//
//	index();

	//	ofstream out("contour", ios::app);
	//	print_label(cout);
}

void TestReachability::inputCmd() {
	while (true) {
		string cmd;
		cin >> cmd;
		if (cmd == "exit") {
			break;
		}

		int n;
		if (cmd != "nlnte" && cmd != "st")
			cin >> n;
		DGraph& g = graph;
		if (cmd == "tf") {
			cout << g.get_tree().father_of(n) << endl;
		} else if (cmd == "ts") {
			Children& c = g.get_tree().children_of(n);
			cout << "children:";
			for (Children::iterator it = c.begin(); it != c.end(); it++) {
				cout << *it << "\t";
			}
			cout << endl;
		} else if (cmd == "tl") {
			cout << "[" << g[n]._PreN << "," << g[n]._DFLN << "],["
					<< g[n]._PreN << "," << g[n]._SupPreN << "]" << endl;
		} else if (cmd == "snte") {
			cout << "short non-tree edges:";
			for (EdgeList::iterator it = g._shortNTE[n].begin(); it
					!= g._shortNTE[n].end(); it++) {
				cout << *it << "\t";
			}
			cout << endl;
		} else if (cmd == "lnte") {
			cout << "long non-tree edges:";
			for (EdgeList::iterator it = g._longNTE[n].begin(); it
					!= g._longNTE[n].end(); it++) {
				cout << *it << "\t";
			}
			cout << endl;
		} else if (cmd == "nlnte") {
			cout << "ni long non-tree edges:";
			for (int j = 0; j < g.number_of_vertices(); j++)
				for (EdgeList::iterator it = g._longNTE[j].begin(); it
						!= g._longNTE[j].end(); it++) {
					if (*it == n) {
						cout << j << "\t";
						break;
					}
				}
			cout << endl;
		} else if (cmd == "slnte") {
			cout << "size of lnte:" << g._longNTE.size() << endl;
		} else if (cmd == "st") {
			cout << "size of the forest:" << g.get_tree().get_roots().size()
					<< endl;
		} else if (cmd == "reach1") {
			int end;
			cin >> end;
			cout << graph.reachViaTree(n, end) << endl;
		} else if (cmd == "reach2") {
			int end;
			cin >> end;
			cout << reach(n, end) << endl;
		}

	}
}
void TestReachability::sortByDFLN() {
	vs2 = graph.get_vertices_withoutrefer();
	sort(vs2.begin(), vs2.end(), dfln_vertices);
}
void TestReachability::GhopContour() {

	vs = graph.get_vertices_withoutrefer();
	sort(vs.begin(), vs.end(), greaterPreN_vertices);

	map<int, hash_set<int> > contour_top;
	map<int, hash_set<int> > temp_gsucc;

	left = 0;

	for (VertexList::iterator vit = vs.begin(); vit != vs.end(); vit++) {
		GhopContour2(vit->_ID, contour, contour_top, temp_gsucc);
	}

	contour_top.clear();

	//	for (int i = 0; i < graph.number_of_vertices(); i++) {
	//		if (gsucc.find(i) != gsucc.end()) {
	//			gsucc[i].insert(i);
	//		}
	//	}

	//	for (VertexList::iterator vit = vs.begin(); vit != vs.end(); vit++) {
	//		if (contour[vit->_ID].size() > 0) {
	//			//			cout<<vit->_ID<<endl;
	//			gsucc[vit->_ID].insert(vit->_ID);
	//		}
	//	}
	//
	for (map<int, hash_set<int> >::iterator ci = contour.begin(); ci
			!= contour.end(); ci++) {

		for (hash_set<int>::iterator is = ci->second.begin(); is
				!= ci->second.end(); is++) {
			upred[*is].insert(ci->first);
		}

	}

}

void TestReachability::GhopContour2(int vid, map<int, hash_set<int> >& contour,
		map<int, hash_set<int> >& contour_top,
		map<int, hash_set<int> >& temp_gsucc) {

	Children& cl = graph.get_tree().children_of(vid);
	SNTEList& shortNTE = graph.get_short_NTEs();
	LNTEList& longNTE = graph.get_long_NTEs();

	hash_set<int> myContour;
	hash_set<int> myContour_temp;
	hash_set<int> myContour_temp2;
	hash_set<int> temp;
	map<int, bool> log;

	//	bool addGsucc = false;

	//	if (graph.lnte_nodes.find(vid)!=graph.lnte_nodes.end())
	//		addGsucc = true;
	//	int mc=0;//debug;


	for (Children::reverse_iterator cit = cl.rbegin(); cit != cl.rend(); ++cit) {
		map<int, hash_set<int> >::iterator mit = contour_top.find(*cit);
		if (mit != contour_top.end()) {
			myContour_temp.insert(mit->second.begin(), mit->second.end());
		}
		//		if (addGsucc) {
		if (graph.lnte_nodes.find(*cit) != graph.lnte_nodes.end()) {
			temp_gsucc[vid].insert(*cit);
		}

		temp_gsucc[vid].insert(temp_gsucc[*cit].begin(), temp_gsucc[*cit].end());
		//		}
	}
	//	cout << "add children's contour " << endl;
	SNTEList::iterator sit = shortNTE.find(vid);
	if (sit != shortNTE.end()) {
		EdgeList& el = sit->second;
		for (EdgeList::iterator eit = el.begin(); eit != el.end(); ++eit) {
			//			if (!visited[*eit])
			//				GhopContour2(visited,*eit, contour, contour_top);
			//			if (*eit == 6074)
			//				rrr = true;
			map<int, hash_set<int> >::iterator mit = contour_top.find(*eit);
			if (mit != contour_top.end()) {
				//				cout << "hahahah22" << endl;
				myContour_temp.insert(mit->second.begin(), mit->second.end());
			}
			//			if (addGsucc) {
			if (graph.lnte_nodes.find(*eit) != graph.lnte_nodes.end()) {
				temp_gsucc[vid].insert(*eit);
			}

			temp_gsucc[vid].insert(temp_gsucc[*eit].begin(),
					temp_gsucc[*eit].end());
			//			}
		}
	}
	//	cout << "add slnte's contour " << endl;

	hash_set<int>::iterator vmits;
	hash_set<int>::iterator vmite;
	bool addFlag;

	for (vmits = myContour_temp.begin(); vmits != myContour_temp.end(); vmits++) {

		addFlag = true;

		for (vmite = myContour.begin(); vmite != myContour.end(); vmite++) {
			if (graph.reachViaTree(*vmite, *vmits)) {
				addFlag = false;
				break;
			}

			if (graph.reachViaTree(*vmits, *vmite)) {
				temp.insert(*vmite);
				break;
			}

		}
		if (temp.size() > 0) {
			for (hash_set<int>::iterator ti = temp.begin(); ti != temp.end(); ti++) {
				myContour.erase(*ti);
			}
			temp.clear();
		}

		if (addFlag) {
			myContour.insert(*vmits);

			//			mc++;
		}
	}
	//	cout << "reduce children's contour " << endl;

	myContour_temp.clear();
	LNTEList::iterator lit = longNTE.find(vid);
	map<int, hash_set<int> >::iterator lmit;
	if (lit != longNTE.end()) {
		//		cout << "ok...." << endl;
		EdgeList& el = lit->second;
		for (EdgeList::iterator eit = el.begin(); eit != el.end(); ++eit) {
			if (graph.reachViaTree(vid, *eit))
				continue;

			myContour_temp.insert(*eit);

			lmit = contour_top.find(*eit);
			if (lmit != contour_top.end())
				myContour_temp.insert(lmit->second.begin(), lmit->second.end());
		}
	}

	//	cout << "add lnte's contour " << endl;

	//	for()

	//	cout << "my contouryy:" << myContour.size() << endl;

	for (vmits = myContour_temp.begin(); vmits != myContour_temp.end(); vmits++) {
		bool addFlag = true;

		for (vmite = myContour.begin(); vmite != myContour.end(); vmite++) {
			if (graph.reachViaTree(*vmite, *vmits)) {
				addFlag = false;
				break;
			} else if (graph.reachViaTree(*vmits, *vmite)) {
				temp.insert(*vmite);
			}
		}

		if (temp.size() > 0) {
			for (hash_set<int>::iterator ti = temp.begin(); ti != temp.end(); ti++) {
				myContour.erase(*ti);

				if (log.find(*ti) != log.end())
					myContour_temp2.erase(*ti);
			}
			temp.clear();
		}

		if (addFlag) {
			myContour.insert(*vmits);
			//			log[*vmits] = true;
			myContour_temp2.insert(*vmits);
			log[*vmits] = true;
		}
	}

	for (hash_set<int>::iterator fit = myContour_temp2.begin(); fit
			!= myContour_temp2.end(); fit++) {
		contour[vid].insert(*fit);
		left++;
	}

	if (myContour.size() > 0)
		contour_top[vid].insert(myContour.begin(), myContour.end());

	if (graph.lnte_nodes.find(vid) != graph.lnte_nodes.end()) {
		gsucc[vid].insert(temp_gsucc[vid].begin(), temp_gsucc[vid].end());
	}
	//	else if (addGsucc)
	//		gsucc[vid].clear();

	myContour.clear();
	myContour_temp.clear();
	myContour_temp2.clear();
	log.clear();

	//	cout << "contour top:" << contour_top[vid].size() << endl;
	//	if (rrr) {
	//		cout << "found 6074" << endl;
	//		exit(0);
	//	}
	//	cout << "over .." << endl;
	//	RTreeFreeListNode(contour_root);
}

int TestReachability::contourSize() {
	int t = 0;
	for (map<int, hash_set<int> >::iterator i = contour.begin(); i
			!= contour.end(); i++) {
		t += i->second.size();
		//		cout << i->first << "-->:";
		//		for (hash_set<int>::iterator is = i->second.begin(); is
		//				!= i->second.end(); is++) {
		//			cout << *is << "\t";
		//		}
		//		cout << endl;
	}
	return t;
}

int TestReachability::contourTopSize(map<int, hash_set<int> >& contour) {
	int t = 0;
	for (map<int, hash_set<int> >::iterator i = contour.begin(); i
			!= contour.end(); i++) {
		t += i->second.size();
		//		cout << i->first << "-->:";
		//		for (hash_set<int>::iterator is = i->second.begin(); is
		//				!= i->second.end(); is++) {
		//			cout << *is << "\t";
		//		}
		//		cout << endl;
	}
	return t;
}

int TestReachability::gsuccSize() {
	int t = 0;
	for (map<int, hash_set<int> >::iterator i = gsucc.begin(); i != gsucc.end(); i++) {
		t += i->second.size();
		//		cout << i->first << "-->:";
		//		for (hash_set<int>::iterator is = i->second.begin(); is
		//				!= i->second.end(); is++) {
		//			cout << *is << "\t";
		//		}
		//		cout << endl;
	}
	return t;
}

void TestReachability::index() {
	int N = graph.number_of_vertices();
	//	int id = 1;
	for (int i = 0; i < N; i++) {
		//		int j;
		for (set<int>::iterator it = _labels[i]._Lin.begin(); it
				!= _labels[i]._Lin.end(); it++) {
			Index_Label label = { { graph[*it]._PreN + N, graph[*it]._DFLN + N,
					graph[i]._PreN + N, graph[i]._DFLN + N, graph[*it]._PreN
							+ N, graph[*it]._DFLN + N, graph[i]._PreN + N,
					graph[i]._DFLN + N } };
			//			Index_Label label = { { graph[*it]._PreN, graph[*it]._DFLN,
			//								graph[i]._PreN, graph[i]._DFLN, graph[*it]._PreN,
			//								graph[*it]._DFLN, graph[i]._PreN, graph[i]._DFLN } };
			//			cout<<graph[*it]._PreN<<","<<graph[*it]._DFLN<<","<<graph[i]._PreN<<","<<graph[i]._DFLN<<flush<<endl;
			//			int id[2] = { *it, i };//int tid[2]={i+1, (i+1)*2};
			RTreeInsertRect(&label, (*it + 1), &root, 0);
		}

		for (set<int>::iterator it = _labels[i]._Lout.begin(); it
				!= _labels[i]._Lout.end(); it++) {
			Index_Label label = { { graph[i]._PreN, graph[i]._DFLN,
					graph[*it]._PreN, graph[*it]._DFLN, graph[i]._PreN,
					graph[i]._DFLN, graph[*it]._PreN, graph[*it]._DFLN } };
			//			cout<<graph[i]._PreN<<","<<graph[i]._DFLN<<","<<graph[*it]._PreN<<","<<graph[*it]._DFLN<<flush<<endl;
			//			int id[2] = { i, *it };
			RTreeInsertRect(&label, (*it + 1), &root, 0);
		}

	}
}

bool TestReachability::test_reach(/*int src, int trg,map<pair<int,int>, bool> tcm*/) {
	map<pair<int, int> , bool> tcm;
	DGraphUtil::transitive_closure_matrix(graph, tcm);
	int src = 0;
	while (src < graph.number_of_vertices()) {
		//		if(src%5==0)
		//			cout<<src<<endl;
		int trg = 0;
		while (trg < graph.number_of_vertices()) {
			bool r = reach(src, trg);
			if (r != tcm[make_pair(src, trg)]) {
				reach2(src, trg);
				cout << "wrong [" << src << "," << trg << "]" << tcm[make_pair(
						src, trg)] << endl;
				exit(0);
				return false;
			}
			trg++;
		}
		src++;
	}
	return true;
}

bool TestReachability::test_reach(int src, int trg) {
	//	if(!(reach(src, trg) == _tcm[make_pair(src, trg)])){
	//		cout<<_tcm[make_pair(src, trg)]<<endl;
	//		exit(0);
	//	}

	return reach(src, trg) == _tcm[make_pair(src, trg)];
}

void TestReachability::test_reach2(int src, int trg) {
	if (!(reach(src, trg) == _tcm[make_pair(src, trg)])) {
		ofstream out("log");

		cout << src << "," << trg << ":" << _tcm[make_pair(src, trg)] << endl;

		printNode(src);
		printNode(trg);

		reach2(src, trg);

		//graph.write_graph(cout);
		graph.write_tree(out);
		graph.write_short_NTEs(out);
		graph.write_long_NTEs(out);
		print_label(out);

		set<int> trueLout;
		set<int> trueLin;

		for (int i = 0; i < graph.number_of_vertices(); i++) {
			if (graph.reachViaTree(src, i)) {
				trueLout.insert(_labels[i]._Lout.begin(),
						_labels[i]._Lout.end());
			}
		}

		for (int i = 0; i < graph.number_of_vertices(); i++) {
			if (graph.reachViaTree(i, trg)) {
				trueLin.insert(_labels[i]._Lin.begin(), _labels[i]._Lin.end());
			}
		}

		//		set<int> toRemove;
		//		for (set<int>::iterator it = trueLout.begin(); it != trueLout.end(); it++) {
		//			if (graph.reachViaTree(src, *it)) {
		//				toRemove.insert(*it);
		//			}
		//		}
		//		for (set<int>::iterator it = toRemove.begin(); it != toRemove.end(); it++) {
		//			trueLout.erase(*it);
		//		}
		//
		//		toRemove.clear();
		//
		//		for (set<int>::iterator it = trueLin.begin(); it != trueLin.end(); it++) {
		//			if (graph.reachViaTree(*it, trg)) {
		//				toRemove.insert(*it);
		//			}
		//		}
		//		for (set<int>::iterator it = toRemove.begin(); it != toRemove.end(); it++) {
		//			trueLin.erase(*it);
		//		}

		cout << "true Lout:";
		for (set<int>::iterator it = trueLout.begin(); it != trueLout.end(); it++) {
			cout << *it << "\t";
		}
		cout << endl;

		cout << "true lin:";
		for (set<int>::iterator it = trueLin.begin(); it != trueLin.end(); it++) {
			cout << *it << "\t";
		}
		cout << endl;

		cout << "debug reach:" << debugReach(src, trg, trueLout, trueLin)
				<< endl;

		inputCmd();

		exit(0);
	}

	//	return reach(src, trg) == _tcm[make_pair(src, trg)];
}

bool TestReachability::debugReach(int src, int trg, set<int>& lout,
		set<int>& lin) {
	for (OutLabel::iterator iout = lout.begin(); iout != lout.end(); iout++) {
		//Lout(src)-->trg?
		if (graph[*iout]._PreN <= graph[trg]._PreN && graph[*iout]._DFLN
				<= graph[trg]._DFLN)
			return true;

		//Lout(src)-->Lin(trg)?
		OutLabel::iterator iin = lin.begin();
		while (iin != lin.end()) {
			if (graph[*iout]._DFLN <= graph[*iin]._DFLN && graph[*iout]._PreN
					<= graph[*iin]._PreN)
				return true;
			iin++;
		}
	}

	InLabel::iterator iin = lin.begin();
	while (iin != lin.end()) {
		if (graph[src]._DFLN <= graph[*iin]._DFLN && graph[src]._PreN
				<= graph[*iin]._PreN)
			return true;
		iin++;
	}

	return false;

}

void TestReachability::printNode(int a) {
	cout << "[" << graph[a]._PreN << "," << graph[a]._DFLN << " ]" << endl;

}

vector<int> result1;
vector<int> result2;

void printVector(vector<int> v) {
	for (vector<int>::iterator ite = v.begin(); ite != v.end(); ite++) {
		cout << *ite << "\t";
	}
	cout << endl;
}

int MySearchCallback1(int id, void* arg) {
	//	cout<<"===="<<endl;
	//	cout<<"found:"<<id<<endl;
	result1.push_back(id - 1);
	// Note: -1 to make up for the +1 when data was inserted
	//	printf("Hit data rect %d\n", id-1);
	return 1; // keep going
}

int MySearchCallback2(int id, void* arg) {
	result2.push_back(id - 1);
	// Note: -1 to make up for the +1 when data was inserted
	//	printf("Hit data rect %d\n", id-1);
	return 1; // keep going
}
bool TestReachability::reach(int src, int trg) {

		int sp = graph[src]._PreN;
		int tp = graph[trg]._PreN;
		int sd = graph[src]._DFLN;
		int td = graph[trg]._DFLN;

		if (sp <= tp) {
			if (sd <= td)
				return true;
		} else {
			return false;
		}

		int i;
		int id;
		int N = graph.number_of_vertices();
		set<int>::iterator sit;
		InLabel in;
		OutLabel out;
		for (i = sp; i <= tp; i++) {
			id = vs[N - i]._ID;

			if (graph[id]._DFLN >= sd) {
				for (sit = _labels[id]._Lout.begin(); sit
						!= _labels[id]._Lout.end(); sit++) {
					if (graph[*sit]._PreN <= tp) {
						if (graph[*sit]._DFLN <= td)
							return true;
						else
							out.insert(*sit);
					}
				}
			} else if (graph[id]._DFLN <= td) {
				for (sit = _labels[id]._Lin.begin(); sit != _labels[id]._Lin.end(); sit++) {
					if (graph[*sit]._PreN >= sp) {
						if (graph[*sit]._DFLN >= sd)
							return true;
						else {

							in.insert(*sit);
						}
					}
				}
			}
		}
		set<int>::iterator eit;

		for (sit = out.begin(); sit != out.end(); sit++) {
			for (eit = in.begin(); eit != in.end(); eit++) {
				if (graph.reachViaTree(*sit, *eit))
					return true;
			}
		}

		return false;
}


bool TestReachability::reach_bak2(int src, int trg) {

	int sp = graph[src]._PreN;
	int tp = graph[trg]._PreN;
	int sd = graph[src]._DFLN;
	int td = graph[trg]._DFLN;

	if (sp <= tp) {
		if (sd <= td)
			return true;
	} else {
		return false;
	}

	int i;
	int id;
	int N = graph.number_of_vertices();
	set<int>::iterator sit;
	InLabel in;
	OutLabel out;
	bool type = true;
//cout<<"reach"<<endl;
	if ((td + 1 + N - sd + 1) < (tp - sp + 1)) {
		type = false;
	}
	if (type) {
		for (i = sp; i <= tp; i++) {
			id = vs[N - i]._ID;
			//		if(i!=graph[id]._PreN){
			//			cout<<"====="<<endl;
			//			exit(0);
			//		}
			if (graph[id]._DFLN >= sd) {
				for (sit = _labels[id]._Lout.begin(); sit
						!= _labels[id]._Lout.end(); sit++) {
					if (graph[*sit]._PreN <= tp) {
						if (graph[*sit]._DFLN <= td)
							return true;
						else
							out.insert(*sit);
					}
					//				else {
					//					in.insert(*sit);
					//				}
				}
			} else if (graph[id]._DFLN <= td) {
				for (sit = _labels[id]._Lin.begin(); sit
						!= _labels[id]._Lin.end(); sit++) {
					if (graph[*sit]._PreN >= sp) {
						if (graph[*sit]._DFLN >= sd)
							return true;
						else {

							in.insert(*sit);
						}
					}
				}
			}
		}


	} else {




		for (i = 0; i < td; i++) {
					id = vs2[i]._ID;

					if (graph[id]._PreN <= tp&&graph[id]._PreN > sp) {
						for (sit = _labels[id]._Lin.begin(); sit
								!= _labels[id]._Lin.end(); sit++) {
							if (graph[*sit]._PreN >= sp) {
								if (graph[*sit]._DFLN >= sd)
									return true;
								else {

									in.insert(*sit);
								}
							}
						}
					}

				}

				for (i = sd-1; i < N; i++) {
					id = vs2[i]._ID;
					if (graph[id]._PreN >= sp&&graph[id]._PreN < tp) {
						for (sit = _labels[id]._Lout.begin(); sit
								!= _labels[id]._Lout.end(); sit++) {
							if (graph[*sit]._PreN <= tp) {
								if (graph[*sit]._DFLN <= td)
									return true;
								else
									out.insert(*sit);
							}
						}
					}
				}
	}

	set<int>::iterator eit;

	for (sit = out.begin(); sit != out.end(); sit++) {
		for (eit = in.begin(); eit != in.end(); eit++) {
			if (graph.reachViaTree(*sit, *eit))
				return true;
		}
	}

	return false;
}
bool TestReachability::reach2(int src, int trg) {
	cout << "==================" << endl;

	if (graph[src]._PreN <= graph[trg]._PreN && graph[src]._DFLN
			<= graph[trg]._DFLN)
		return true;

	result1.clear();
	result2.clear();

	int N = graph.number_of_vertices();

	Index_Label search_rect_s1 = { { graph[src]._PreN, graph[src]._DFLN,
			graph[src]._PreN, 1, N, N, N, graph[src]._DFLN } };
	Index_Label search_rect_s2 = { { graph[src]._PreN, graph[src]._DFLN, 1,
			graph[src]._DFLN, N, N, graph[src]._PreN, N } };

	RTreeSearch(root, &search_rect_s1, MySearchCallback1, 0);
	RTreeSearch(root, &search_rect_s2, MySearchCallback1, 0);

	//	Index_Label search_rect_e1 = { { graph[src]._PreN, 0, 0, 0, N,
	//			graph[src]._DFLN, graph[trg]._PreN, graph[trg]._DFLN } };
	//	Index_Label search_rect_e2 = { { 0, graph[src]._DFLN, 0, 0,
	//			graph[src]._PreN, N, graph[trg]._PreN, graph[trg]._DFLN }, };

	Index_Label search_rect_e1 = { { graph[trg]._PreN + N, N + 1, N + 1, N + 1,
			N + N, graph[trg]._DFLN + N, graph[trg]._PreN + N, graph[trg]._DFLN
					+ N } };
	Index_Label search_rect_e2 = { { N + 1, graph[trg]._DFLN + N, N + 1, N + 1,
			graph[trg]._PreN + N, N + N, graph[trg]._PreN + N, graph[trg]._DFLN
					+ N }, };

	//	Index_Label search_rect_e1 = { { graph[trg]._PreN, 1, 1,1, N,
	//				graph[trg]._DFLN, graph[trg]._PreN, graph[trg]._DFLN } };
	//		Index_Label search_rect_e2 = { { 1, graph[trg]._DFLN, 1, 1,
	//				graph[trg]._PreN, N, graph[trg]._PreN, graph[trg]._DFLN }, };

	//	search_rect_s1 = { { graph[src]._PreN, 0,
	//				graph[src]._PreN, 0, N, N, N, graph[src]._DFLN } };
	//	search_rect_s2 = { { graph[src]._PreN, graph[src]._DFLN, 0,
	//				graph[src]._DFLN, N, N, graph[src]._PreN, N } };


	RTreeSearch(root, &search_rect_e1, MySearchCallback2, 0);
	RTreeSearch(root, &search_rect_e2, MySearchCallback2, 0);

	//	cout<<"size of 1:"<<result1.size()<<endl;
	//	cout<<"size of 2:"<<result2.size()<<endl;
	sort(result1.begin(), result1.end());
	sort(result2.begin(), result2.end());

	cout << "Lout:";
	printVector(result1);
	cout << "Lin:";
	printVector(result2);

	for (vector<int>::iterator ite = result2.begin(); ite != result2.end(); ite++) {
		if (graph.reachViaTree(src, *ite))
			return true;
	}

	if (result1.size() == 0)
		return false;

	for (vector<int>::iterator it = result1.begin(); it != result1.end(); it++) {
		if (graph.reachViaTree(*it, trg))
			return true;
		for (vector<int>::iterator ite = result2.begin(); ite != result2.end(); ite++) {
			if (graph.reachViaTree(*it, *ite))
				return true;
		}
	}

	cout << "==================" << endl;
	return false;
}

DGraph& TestReachability::getGraph() {
	return graph;
}

void TestReachability::caculateTransitiveClosure() {
	DGraphUtil::transitive_closure_matrix(graph, _tcm);
}

bool TestReachability::equalto(const double a, const double b) {
	return abs(a - b) < FLT_EPSILON;
}
